Write a program that declares an array of size 1,230 and stores the first 1,230 prime numbers in this array. The program then uses the first 1,230 prime numbers to determine if a number between 2 and 100,000,000 is prime. If a number is not prime, then output at least one of its prime factors.

The complete question is :

A positive integer n is called prime if n > 1 and the only factors of n are 1 and n. It is known that the positive integer n>1 is prime if n is not divisible by any prime integer m≤n. The 1230th prime number is 10,007. Let t be an integer such that 2≤t≤100,000,000. Then t is prime if either t is equal to one of the first 1230 prime numbers or t is not divisible by any of the first 1230 prime numbers. Write a program that declares an array of size 1,230 and stores the first 1,230 prime numbers in this array. The program then uses the first 1,230 prime numbers to determine if a number between 2 and 100,000,000 is prime. If a number is not prime, then output at least one of its prime factors.

Explanation:

The program is :

#include<iostream>  

#include<cmath>  

using namespace std;  

const int SIZE = 1230;  

bool isPrime(int number);  

void first1230PrimeNum(int list[], int length);  

void primeTest(int num, int list[], int length);

int main()  

{

   int primeList[SIZE];

   int number;

    first1230PrimeNum(primeList, SIZE);

    cout<<"Enter an integer between 2 and 100,000,000: ";

    cin>>number;

    cout<<endl;

    primeTest(number, primeList, SIZE);

    system("pause");

     return 0;

}  

bool isPrime(int number)  

{

 int i; //to iterate

  //loop till sqrt(number)

    for(i=2; i<=sqrt(number); i++)

      {

         //if any factor

         if(number%i == 0)

          return false;//return false

     }

        return true; //otherwise return true

}  

void first1230PrimeNum(int list[], int length)  

{

 int i=0, number = 2; //i to itrate and number to test prime

 while(i<length) //get 1230 primes

   {

    if(isPrime(number)) //check if prime or not

    {

      list[i] = number; //add it to list

      i++; //increment i

    }

 number++; //increment number

  }  

}  

void primeTest(int num, int list[], int length)  

{

int i; //i to iterate

 //loop through list

 for(i=0; i<length; i++)

{

//if num is in list then it is prime

  if(num == list[i])

 {

  cout<<num<<" is a prime"<<endl;

   return;

   }

   //if divisible by any number then not a prime

    if(num % list[i] == 0)

{

  cout<<num<<" is not a prime"<<endl;

   cout<<"One of the prime factor: "<<list[i]<<endl;

   return;

 }

}

cout<<num<<" is a prime"<<endl;  

}

OUTPUT :

Enter an integer between 2 and 100,000,000 : 104659

104659 is a prime.