-
prime number algorithm
Can anyone help me getting started with a prime number algorithm? I am stuck at the modulus operator. Ok if I read in a number from a file and use it as a limit for a loop, how can I find all the prime numbers inbetween 2 and this limit?
I've tried doing
int inputNumber;
inFile >> inputNumber;
isPrime(inputNumber);
///// ********/////
BOOL isPrime(int value)
{
int counter;
for(counter = 2; counter <= value; counter++)
if((value % counter) == 0)
blah
This obviously is not the correct method for doing this as 9, for example, will be declared a prime number when it isn't. Does anyone have any ideas?
TIA
-
it cant be <= it must be <. Otherwise 9/9 has no remainder!
Close....
-
The other thing is that your counter only needs to go as far as value / 2...... anything above this you've already checked with the preceding counter values.
Cheers,
Rob.
Doh! knew I shoulda checked first..... you only need to go as far as sqrt value.
-
>I am stuck at the modulus operator.
It gets the remainder. If N and M are both integers, then the remainder can be calculated as
N mod M = N - (N/M) * M
Keep in mind that we're using integers. So 21/4=5.
Example:
21 / 4 = 5
21 %4 = 21 - 5 * 4
This operator can be check if a certain number N is a prime number. The number N is prime iff for each number M between 1 and N the expression (N mod M == 0) evaluates to FALSE. In other words, N should not be divisible by any number M between 1 and N.
So you need a loop with a variable which represents M and then calculate (N mod M) and check if it is equal to 0 or not.
-
Thanks for the replies everyone, but this thing still isn't working right. I pass the first value from the input file into the bool function, so if the value is 19, the bool function should return true. Once I know it's true, then I need to pass that number along to obtain all the prime numbers from 2 up until and including that number. As in the above example, 19, I should get 2,5,7,11,13,17, and 19 as all prime numbers. However, this bool function is not correctly passing along which numbers are prime.
I've got an input file with integers from 0-30 to test this. The bool function is returning 9, 15, 21, 25, 27 as being prime.
My bool function
bool isPrime(int prime)
{
for(int i = 2; i < sqrt(prime); i++)
if(prime % i == 0)
return false;
else
return true;
}
There is a logic error in here somewhere. When this function returns true, do I need to check the returning number again without using the sqrt(num) type of operation? Also, should I use an array to store these prime numbers, or write each prime number directly one at a time?
My other functions are
void writeFile(ofstream&, int);
void readFile(ifstream&);
void printFile(ifstream&);
These are working I *think*. Any other ideas would be appreciated.
Thanks again
-
In the code
bool isPrime(int prime)
{
for(int i = 2; i < sqrt(prime); i++)
if(prime % i == 0)
return false;
else
return true;
}
If prime = 9, int only goes to 2, not 3.
Try
for(int i = 2; i <= sqrt(prime); i++)
or alternatively
for(int i = 2; i < sqrt(prime)+1 ; i++)
Hope this helps.
-
if you want to check for all prime numbers between 2 and a given value you need to use a nested loop
Code:
int givenValue;
int i;
int j;
for (i = 2; i <= givenValue; i++) //check every number less than or equal to a given value to see if it is prime
{
//algorhythm to determine if i is prime
for(j = 0; j < i/2; i++)
{
//etc.
}
}
-
How about:
bool isPrime(int prime) {
if (prime == 2) return true; // We know 2 is a prime
if (prime % 2 ==0) return false; //Since we're starting at 3 int the loop
for(int i = 3; i <=(prime / 2); i+=2) { // increment by 2 for speed
if(prime % i == 0) return false;
}
return true;
}
If you want to save even more time, build an array or list of previously found primes and mod by these instead of using a loop that contains non-primes (i.e why mod by 15 when mod by the primes 3 or 5 will give the answer).
-
i think this could be done an easier way using newbish methods...and for statements...and loops... im going to attempt this...
10 minutes later...
ok i couldnt figure it out...its too hard :( for my newbish mind
-
Just use the sieve of eratosthenes. I made a program like this a little bit ago, I'll post the source. Just replace arraysize with whatever you read from the file, and you'll be set.
#include <iostream>
#define arraysize 1000
using namespace std;
void main()
{
int primes[arraysize] = {1};
int pause;
/*garbage variable, used to stop the text from scrolling for a moment.*/
for (int i = 2; i <= arraysize/2; i++)
{
for (int j = 2; (j * i) < arraysize; j++)
{
primes[j * i] = 1;
}
}
for (i = 1; i < arraysize; i++)
{
if (primes[i] == 0)
cout<< i << " is a prime number." << endl;
if ((i % 50) == 0)
{
cout << "Enter any number to continue."<<endl;
cin >> pause;
}
}
}
-
-
Will: cool algorhythm, but should primes[] be initialzed to all 0's instead of 1's? Otherwise I don't see how primes[i] could ever be 0.
-
WOW!! Thanks to all who replied. I'll have to sift through the coding examples and the link above. I have a strange feeling that this program should not have given me such a hard time. :)
