首頁  >  文章  >  後端開發  >  暴風雨數字

暴風雨數字

PHPz
PHPz轉載
2023-08-26 09:41:171191瀏覽

暴風雨數字

For N to be a stormer number, the highest prime factor of the expression N^2 1 must be greater than or equal to 2*N and it should be a positive integer.

For example, 4 is a stormer number. Since 4*4 1=17 has the greatest prime factor 17 itself which is greater than 8 i.e. 2*4.

但是3不是一個強力數字,因為3*3 1=10。10的最大質因數是5,小於6即2*3。

在這個問題中,我們給定一個正整數N,我們的目標是列印出前N個stormer。

輸入: 4

OUTPUT: 1 2 4 5

這裡是前4個斯托默數。 3不是斯托默數,所以沒有包括在內。

演算法

  • 找到數字(N^2 1)的最大質因數,並將其儲存在任意變數中。

  • Check if the prime factor is larger than or equal to 2*N.

  • If it satisfies the condition hence it is a stormer number.

  • Print all the stormer numbers until i is less than or equal to N.

#方法

To implement the above algorithm in our code, we need to make two functions. First, to find out the highest prime factor for each case and second to check if it is greater than or equal to 2*N and keep print if it is greater than or equal to 2*N and keeping the number if it is a stormer number simultaneously.

For finding out the highest prime factor of expression (n^2 1) for every number n −

  • We will divide the number by 2 until it gives remainder 0 and store 2 in primemax.

  • #現在,n在這一點上必須是奇數,所以我們將在一個for循環中迭代,只迭代從i=3到n的平方根的奇數。

  • Now store i in primemax and divide n by i while i divides n. When i fails to divide n then raise it by 2 and carry on.

  • 如果n是一個大於2的質數,那麼在前兩個步驟中n不會變成1,因此我們將n儲存在primemax中並傳回primemax。

The next function will be to check if the number is a stormer number or not. If it is, we will print it.

  • 我們將宣告一個變數 temp 為 0,以計算前 N 個 stormer 數。

  • 從i=1開始,在temp小於N之前進行for迴圈迭代。

  • 檢查 (i*i 1) 是否有大於或等於 2*i 的最大質因數。如果上述條件為真,則列印 i 並將 temp 增加 1。

Example

的中文翻譯為:

範例

Below is the implementation of above approach in C −

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int prime_factor(int n){ //for finding the maximum prime factor
   int primemax=0;
   while(n%2==0){ //if n is divided by 2 than we store 2 in primemax 
      primemax=2;
      n=n/2;
   }
   for(int i=3;i<=sqrt(n);i+=2){ // this is only for odd number 
      while(n%i==0){
         primemax=i;
         n=n/i;
      }
   }
   if(n>2){ // when n is prime number and greater than 2 
      primemax=n;
   }
   return primemax;
}
void stormer_number(int n){  //function to print first n stormer numbers
   int temp=0; // for counting the stormer number 
   for(int i=1;temp<n;i++){  // for iterating the all number 
      int check=(i*i)+1;  // for storing the (i*i)+1 value in check
      if(prime_factor(check)>=(2*i)){ //for checking the number if maximum prime is greater or equal to 2*i
         cout<<i<<" ";
         temp++;
      }
   }
}
int main(){
   int n=9;
   stormer_number(n);
   
   return 0;
}

Output

#
1 2 4 5 6 9 10 11 12

結論

在本文中,我們嘗試解決列印前 N 個斯托默數的問題。

我們也學會了計算一個數的質因數。我希望這篇文章能幫助解決您對這個問題的所有疑惑。

以上是暴風雨數字的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除