storm numbers

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.

But 3 is not a strong number, because 3*3 1=10. The largest prime factor of 10 is 5, which is less than 6, which is 2*3.

In this problem, we are given a positive integer N, and our goal is to print out the first N stormers.

Input: 4

OUTPUT: 1 2 4 5

Here are the first 4 Stormer numbers. 3 is not a Stormer number, so it is not included.

algorithm

• Find the largest prime factor of the number (N^2 1) and store it in an arbitrary variable.

• 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.

method

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 printing 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.

• Now, n must be an odd number at this point, so we will iterate in a for loop and only iterate the odd numbers from i=3 to the square root of 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.

• If n is a prime number greater than 2, then n will not become 1 in the first two steps, so we store n in primemax and return primemax.

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

• We will declare a variable temp as 0 to calculate the first N stormer numbers.

• Start from i=1 and perform for loop iteration before temp is less than N.

• Check whether (i*i 1) has the largest prime factor greater than or equal to 2*i. If the above condition is true, print i and increment temp by 1.

The Chinese translation of

Example

is:

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

in conclusion

In this article, we try to solve the problem of printing the first N Stormer numbers.

We also learned to calculate the prime factors of a number. I hope this article helps clear up all your doubts about this issue.

The above is the detailed content of storm numbers. For more information, please follow other related articles on the PHP Chinese website!