
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 030 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 nonprimes (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. :)