find nth prime issue
I ran into some trouble trying to find the nth prime number. Help!
#include<iostream>
using namespace std;
int isPrime (int num) {
int nPrime = num+1;
int pCounter = 0;
bool IsPrime = true;
while (IsPrime == true) {
for (int i = 2; i < nPrime; i++) {
if (nPrime % i == 0) {
pCounter ++;
break;
}
}
if (pCounter == 0) {
IsPrime = true;
pCounter = 0;
return nPrime;
} else {
nPrime++;
pCounter = 0;
}
}
return 0;
}
int main ()
{
int a;
int nPrime;
char IsPrime;
char res;
cout<< "F: Find the nth prime number\n";
cout << "T: Test a value to see if it is prime\n";
cout << "Q: Terminate the program\n";
cout<<"Next step [F/T/Q]\n";
if(res=='T'||res=='t'){
cout<<"Enter a positive integer: ";
cin >> nPrime;
if(IsPrime)
cout<<"This is a Prime Number\n";
else
cout<< "This is NOT a Prime Number\n";
}
if(res=='F'||res=='f'){
while (a<=0)
{ cout<<"Enter a positive integer: ";
cin>>a;
continue;
}
cout<<"the "<<a<<" th prime number is: "<< isPrime(a) <<"\n";
}
if(res=='Q'||res=='q'){
}
return 0;
}
#include<iostream>
using namespace std;
int isPrime (int num) {
int nPrime = num+1;
int pCounter = 0;
bool IsPrime = true;
while (IsPrime == true) {
for (int i = 2; i < nPrime; i++) {
if (nPrime % i == 0) {
pCounter ++;
break;
}
}
if (pCounter == 0) {
IsPrime = true;
pCounter = 0;
return nPrime;
} else {
nPrime++;
pCounter = 0;
}
}
return 0;
}
int main ()
{
int a;
int nPrime;
char IsPrime;
char res;
cout<< "F: Find the nth prime number\n";
cout << "T: Test a value to see if it is prime\n";
cout << "Q: Terminate the program\n";
cout<<"Next step [F/T/Q]\n";
if(res=='T'||res=='t'){
cout<<"Enter a positive integer: ";
cin >> nPrime;
if(IsPrime)
cout<<"This is a Prime Number\n";
else
cout<< "This is NOT a Prime Number\n";
}
if(res=='F'||res=='f'){
while (a<=0)
{ cout<<"Enter a positive integer: ";
cin>>a;
continue;
}
cout<<"the "<<a<<" th prime number is: "<< isPrime(a) <<"\n";
}
if(res=='Q'||res=='q'){
}
return 0;
}
Last edited on
What is the problem you ran into?
To improve efficiency somewhat:
1 - A prime number is a number larger than 1 that can not be divided without remainder by any other prime number, so if you create a list/vector of the prime numbers that you have found you can skip a lot of values when testing if a value is a prime number.
2 - To check if a number X is a prime number you only have to check if it can be divided by any value Y where Y <= (X/2).
Suppose you have found: 2 3 5 7 11 13 17 19 23 29 31
And now you want to check if 37 is a prime number, you could check all 35 numbers, but you only need to test 7 of them.
To improve efficiency somewhat:
1 - A prime number is a number larger than 1 that can not be divided without remainder by any other prime number, so if you create a list/vector of the prime numbers that you have found you can skip a lot of values when testing if a value is a prime number.
2 - To check if a number X is a prime number you only have to check if it can be divided by any value Y where Y <= (X/2).
Suppose you have found: 2 3 5 7 11 13 17 19 23 29 31
And now you want to check if 37 is a prime number, you could check all 35 numbers, but you only need to test 7 of them.
Thanks! My question is that it did not output correct prime count, and the program will not let me input response.
Topic archived. No new replies allowed.