Given a number ‘n’, the task is to generate the first ‘n’ Stormer numbers.
A Stormer Number is a positive integer ‘i’ such that the greatest prime factor of the term 
is greater than or equal to .
For example, 5 is a Stormer number because the greatest prime factor of 26(i.e 5*5 + 1) is 13 which is greater than or equal to 10(i.e 2*5)
Input : 5
Output : 1 2 4 5 6
Here 3 is not a Stormer number because the greatest prime
factor of 10(i.e 3*3 + 1) is 5, which is not greater than
or equal to 6(i.e 2*3)
Input : 10
Output : 1 2 4 5 6 9 10 11 12 14
- For a number ‘i’, first find the largest prime factor of the number i*i + 1.
- Next, test whether that prime factor is greater than or equal to 2*i.
- If it is greater then ‘i’ is a Stormer number.
Below is the implementation of above approach:
C++
// C++ program to print // Stormer numbers // Function to find // largest prime factor#include <bits/stdc++.h>using namespace std; int maxPrimeFactors(int n) { // Initialize the maximum // prime factor variable // with the lowest one int maxPrime = -1; // Print the number of // 2's that divide n while(n % 2 == 0) { maxPrime = 2; n /= 2; } // n must be odd at this // point, thus skip the // even numbers and iterate // only for odd integers for(int i = 3; i < (int)(sqrt(n)+ 1); i += 2) while(n % i == 0) { maxPrime = i; n /= i; } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) maxPrime = n; return (int)(maxPrime); } // Function to generate // Stormer Numbers int stormer(int n) { int i = 1; // Stores the number of // Stormer numbers found int count = 0; while(count < n) { int t = i * i + 1; if (maxPrimeFactors(t) >= 2 * i) { cout << i ; cout <<" "; count += 1; } i += 1; } return i; } // Driver Code int main() { int n = 10; stormer(n); } |
Java
// Java program to print // Stormer numbers // Function to find // largest prime factor import java.io.*;class GFG {static int maxPrimeFactors(int n) { // Initialize the maximum // prime factor variable // with the lowest one int maxPrime = -1; // Print the number of // 2's that divide n while(n % 2 == 0) { maxPrime = 2; n /= 2; } // n must be odd at this // point, thus skip the // even numbers and iterate // only for odd integers for(int i = 3; i < (int)(Math.sqrt(n)+ 1); i += 2) while(n % i == 0) { maxPrime = i; n /= i; } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) maxPrime = n; return (int)(maxPrime); } // Function to generate // Stormer Numbers static int stormer(int n) { int i = 1; // Stores the number of // Stormer numbers found int count = 0; while(count < n) { int t = i * i + 1; if (maxPrimeFactors(t) >= 2 * i) { System.out.print (i +" "); count += 1; } i += 1; } return i;} // Driver Code public static void main (String[] args) { int n = 10; stormer(n); }}//This code is contributed akt_mit |
Python3
# Python program to print Stormer numbersfrom __future__ import print_function# Function to find largest prime factordef maxPrimeFactors(n): # Initialize the maximum prime factor # variable with the lowest one maxPrime = -1 # Print the number of 2's that divide n while n % 2 == 0: maxPrime = 2 n /= 2 # n must be odd at this point, thus skip # the even numbers and iterate only for # odd integers for i in range(3, int(n**0.5)+1, 2): while n % i == 0: maxPrime = i n /= i # This condition is to handle the case when # n is a prime number greater than 2 if n > 2: maxPrime = n return int(maxPrime)# Function to generate Stormer Numbersdef stormer(n): i = 1 # Stores the number of Stormer numbers found count = 0 while(count < n): t = i * i + 1 if maxPrimeFactors(t) >= 2 * i: print(i, end =' ') count += 1 i += 1# Driver Methodif __name__=='__main__': n = 10 stormer(n) |
C#
// C# program to print // Stormer numbers using System;// Function to find // largest prime factor public class GFG{ static int maxPrimeFactors(int n) { // Initialize the maximum // prime factor variable // with the lowest one int maxPrime = -1; // Print the number of // 2's that divide n while(n % 2 == 0) { maxPrime = 2; n /= 2; } // n must be odd at this // point, thus skip the // even numbers and iterate // only for odd integers for(int i = 3; i < (int)(Math.Sqrt(n)+ 1); i += 2) while(n % i == 0) { maxPrime = i; n /= i; } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) maxPrime = n; return (int)(maxPrime); } // Function to generate // Stormer Numbers static int stormer(int n) { int i = 1; // Stores the number of // Stormer numbers found int count = 0; while(count < n) { int t = i * i + 1; if (maxPrimeFactors(t) >= 2 * i) { Console.Write(i +" "); count += 1; } i += 1; } return i; } // Driver Code static public void Main (){ int n = 10; stormer(n); } } //This code is contributed akt_mit |
PHP
<?php// PHP program to print// Stormer numbers// Function to find // largest prime factorfunction maxPrimeFactors($n){ // Initialize the maximum // prime factor variable // with the lowest one $maxPrime = -1; // Print the number of // 2's that divide n while($n % 2 == 0) { $maxPrime = 2; $n /= 2; } // n must be odd at this // point, thus skip the // even numbers and iterate // only for odd integers for($i = 3; $i < (int)(sqrt($n)+ 1); $i += 2) while($n % $i == 0) { $maxPrime = $i; $n /= $i; } // This condition is to handle // the case when n is a prime // number greater than 2 if ($n > 2) $maxPrime = $n; return (int)($maxPrime);}// Function to generate// Stormer Numbersfunction stormer($n){ $i = 1; // Stores the number of // Stormer numbers found $count = 0; while($count < $n) { $t = $i * $i + 1; if (maxPrimeFactors($t) >= 2 * $i) { echo $i." "; $count += 1; } $i += 1; }}// Driver Code$n = 10;stormer($n);// This code is contributed// by mits?> |
Javascript
<script> // Javascript program to print Stormer numbers // Function to find largest prime factor function maxPrimeFactors(n) { // Initialize the maximum // prime factor variable // with the lowest one let maxPrime = -1; // Print the number of // 2's that divide n while(n % 2 == 0) { maxPrime = 2; n = parseInt(n / 2, 10); } // n must be odd at this // point, thus skip the // even numbers and iterate // only for odd integers for(let i = 3; i < parseInt(Math.sqrt(n)+ 1); i += 2) while(n % i == 0) { maxPrime = i; n = parseInt(n / i, 10); } // This condition is to handle // the case when n is a prime // number greater than 2 if (n > 2) maxPrime = n; return (maxPrime); } // Function to generate // Stormer Numbers function stormer(n) { let i = 1; // Stores the number of // Stormer numbers found let count = 0; while(count < n) { let t = i * i + 1; if (maxPrimeFactors(t) >= 2 * i) { document.write(i +" "); count += 1; } i += 1; } return i; } let n = 10; stormer(n); // This code is contributed by rameshtravel07.</script> |
Output:
1 2 4 5 6 9 10 11 12 14
Time Complexity: O(k * sqrt(k)) where k is the nth Stormer number.
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
