Smallest composite number not divisible by first N prime numbers | C ++ Program to implement the above approach ; Initializing the max value ; Function to generate N prime numbers using Sieve of Eratosthenes ; Stores the primes ; Setting all numbers to be prime initially ; If a prime number is encountered ; Set all its multiples as composites ; Store all the prime numbers ; Function to find the square of the ( N + 1 ) - th prime number ; Driver Code ; Stores all prime numbers
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_SIZE  1000005 NEW_LINE void SieveOfEratosthenes ( vector < int > & StorePrimes ) { bool IsPrime [ MAX_SIZE ] ; memset ( IsPrime , true , sizeof ( IsPrime ) ) ; for ( int p = 2 ; p * p < MAX_SIZE ; p ++ ) { if ( IsPrime [ p ] == true ) { for ( int i = p * p ; i < MAX_SIZE ; i += p ) IsPrime [ i ] = false ; } } for ( int p = 2 ; p < MAX_SIZE ; p ++ ) if ( IsPrime [ p ] ) StorePrimes . push_back ( p ) ; } int Smallest_non_Prime ( vector < int > StorePrimes , int N ) { int x = StorePrimes [ N ] ; return x * x ; } int main ( ) { int N = 3 ; vector < int > StorePrimes ; SieveOfEratosthenes ( StorePrimes ) ; cout << Smallest_non_Prime ( StorePrimes , N ) ; return 0 ; }