Answer:
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.
