Thread: prime number algorithm

  1. #1
    Unregistered
    Guest

    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. #2
    Registered User
    Join Date
    Jan 2002
    Posts
    75
    it cant be <= it must be <. Otherwise 9/9 has no remainder!
    Close....

  3. #3
    www.entropysink.com
    Join Date
    Feb 2002
    Posts
    603
    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.
    Last edited by RobR; 02-22-2002 at 07:40 AM.

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    >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. #5
    Unregistered
    Guest
    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

  6. #6
    www.entropysink.com
    Join Date
    Feb 2002
    Posts
    603
    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. #7
    Unregistered
    Guest
    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.
          }
    }

  8. #8
    Registered User
    Join Date
    Jan 2002
    Posts
    18
    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).
    Last edited by linuxgeek; 02-22-2002 at 03:17 PM.
    I doubt, therefore I might not be

  9. #9
    Registered User Paro's Avatar
    Join Date
    Feb 2002
    Posts
    160
    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
    Paro

  10. #10
    Registered User
    Join Date
    Dec 2001
    Posts
    28
    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. #11
    www.entropysink.com
    Join Date
    Feb 2002
    Posts
    603

  12. #12
    Unregistered
    Guest
    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.

  13. #13
    Unregistered
    Guest
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  2. how do i calculate prime number
    By pimp in forum C Programming
    Replies: 50
    Last Post: 01-12-2008, 10:25 PM
  3. Replies: 6
    Last Post: 11-04-2002, 05:11 PM
  4. prime # query
    By alokin in forum C Programming
    Replies: 8
    Last Post: 09-04-2002, 11:50 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM