1. ## 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

2. it cant be <= it must be <. Otherwise 9/9 has no remainder!
Close....

3. 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.

4. >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.

5. 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 printFile(ifstream&);

These are working I *think*. Any other ideas would be appreciated.

Thanks again

6. 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.

7. 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.
}
}

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).

9. 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

10. 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;
}
}
}

11. 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.

12. 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.