Jump to content
  • Advertisement
Sign in to follow this  
Servant of the Lord

Finding Prime Numbers

This topic is 4481 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For programming practice I decided to make a program which finds prime numbers. As many programs do this already, it shouldn't be to hard nor take more than a few hours. *cough* I started three days ago. Each day I started to make one and realized I was going about it the wrong way, so I restarted the following day. I started out simply enough, but my first prog wouldn't compile. My second prog, after two or three hours of coding; or an hour of coding and two of being lazy and just surfing the web; it compiled! Only problem was that some of the numbers it spat out weren't primes. [sad] Today, however, I got it to work, and as far as I can see, it gives me numbers that are actaully primes. All the numbers from 0 to 50 it gave me were in fact primes, upon me checking with a piece of paper the old way. The problem is that it finds the primes and then outputs them, which is fine for the primes between zero and a thousand, but any higher and it takes ages before it drops a single number. I remade it, and it works marginaly faster. It now prints each prime as it finds it and I got rid of unneccasary code. It, however, slows slightly more with each number it spat out, so once in the ten thousands it takes about a second per prime(way to slow if you think about it). I will post all three(or four really) programs so you can see my progress if you like. My actual question here is: Using the fourth program(at the very bottom of the post) how would you upgrade it to perform faster? Please comment your changes. Thanks. First project: (Can't compile)
#include <iostream>
using namespace std;

typedef unsigned long int ULI;
ULI Number, RiseNumber, Save, P2, P3, P5, P7;
int Max2, Max3, Max5, Max7, i, skip;
string Again;
int main()
{
    Again = "Y";
    cout << "\t::Prime Finder::\n"
         << "Find all the prime numbers between\n"
         << "your number and zero. Your number?\n";
    while(Again != "N" && Again != "n")
    {
        cout << ">> ";
        cin >> Number;
        RiseNumber = 0;
        P2, P3, P5, P7 = 0;
        i = 0;
        while(P2 < Number)
        {
            P2 += 2;
            ULI P2[i++] = P2;
        }
        Max2 = i;
        i = 0;
        while(P3 < Number)
        {
            P3 += 3;
            ULI P3[i++] = P3;
        }
        Max3 = i;
        i = 0;
        while(P5 < Number)
        {
            P5 += 5;
            ULI P5[i++] = P5;
        }
        Max5 = i;
        i = 0;
        while(P7 < Number)
        {
            P7 += 7;
            ULI P7[i++] = P7;
        }
        Max7 = i;
        i = 0;
        SaveNum[A]
        ULI LoopCount;
        while(LoopCount != Number)
        {
            RiseNumber++;
            int M2 = Max2 + 1;
            int M3 = Max3 + 1;
            int M5 = Max5 + 1;
            int M7 = Max7 + 1;
            while(M2 != 0)
            {
                if(P2[M2--] != RiseNumber)
                {
                    RiseNumber = Save
                }
                if(M3 != 0){
                if(P3[M3--] != RiseNumber)
                {
                    
                }}
                if(M5 != 0){
                if(P5[M5--] != RiseNumber)
                {
                    
                }}
                if(M7 != 0){
                if(P7[M7--] != RiseNumber)
                {
                    
                }}
            }
            
            
        }
        
        P2 += 2;
        P3 += 3;
        P5 += 5;
        P7 += 7;
        RiseNumber++;
            
        
            
            
  
        while(Again != "Y" && Again != "y" && Again != "N" && Again != "n")
        {
            cout << "Again?\n Y/N\n";
            cin >> Again;
        }
    }
    return 0;
}

Note: I know now the reason this doesn't compile; I needed to use vectors not arrays. Second project: (gives more than primes)
#include <iostream>
using namespace std;

unsigned long int Number, RaiseNum, TestNum;
int i, GoOn;
int main()
{
    bool Stop = 0;
    RaiseNum = 1;
    TestNum = 0;
    i = 4;
    cout << "\n\t::Prime Finder::\n"
         << "Type in any number to find all the positive\n"
         << "primes it contains. What is your number?\n>> ";
    cin >> Number;
    cout << "2,3,5,7,";
    while(i != 6)
    {
        if(RaiseNum > Number)
        {
            cout << "\n\tAll the primes are listed.\n";
            Stop = 1;
        }
        if(Stop == 1)
        {
            system("pause");
            return 0;
        }
        bool P2 = 0, P3 = 0, P5 = 0, P7 = 0;
        RaiseNum++;
        TestNum = 0;
        while(P2 == 0)
        { 
            TestNum += 2;
            if(TestNum == RaiseNum)
            {
                GoOn = 0;
                P2 = 1;
                P3 = 1;
                P5 = 1;
                P7 = 1;
            }
            if(TestNum > Number)
            {
                GoOn++;
                P2 = 1;
            }
        }
        TestNum = 0;
        while(P3 == 0)
        {
            TestNum += 3; 
            if(TestNum == RaiseNum)
            {
                GoOn = 0;
                P3 = 1;
                P5 = 1;
                P7 = 1;
            }
            if(TestNum > Number)
            {
                GoOn++;
                P3 = 1;
            }
        }
        TestNum = 0;
        while(P5 == 0)
        {
            TestNum += 5; 
            if(TestNum == RaiseNum)
            {
                GoOn = 0;
                P5 = 1;
                P7 = 1;
            }
            if(TestNum > Number)
            {
                GoOn++;
                P5 = 1;
            }
        }
        TestNum = 0;
        while(P7 == 0)
        {
            TestNum += 7;
            if(TestNum == RaiseNum)
            {
                GoOn = 0;
                P7 = 1;
            }
            if(TestNum >= Number)
            {
                GoOn++;
                P7 = 1;
            }
        }
        if(GoOn == 4)
        {
            i++;
            cout << RaiseNum << ",";
            TestNum = 0;
            if(i == 5)
            {
                i = 0;
                cout << endl;
            }
            GoOn = 0;
        }
    }
}

Note: The reason that it gives more than primes is because I had my prime finding style wrong; it only gets rid of the numbers that are multiples of 2,3,5, and 7 as opposed to all previously found primes. Third project: (Finds all the primes and then posts them - too slow)
#include <iostream>
#include <vector>
using namespace std;

typedef unsigned long int ULI;
ULI List, i, Number, Counter, RiseNumber, A;
vector <ULI> Primes(0);

int FindPrime()
{
    Counter = 1;
    bool Save = 1;
    while(Counter <= Number)
    {
        Counter += 2;
        RiseNumber = 1;
        while(RiseNumber <= Number)
        {
            RiseNumber++;
            if(List == (Counter * RiseNumber))
            {
                Save = 0;
                Counter = Number + 1;
            }
        }
    }
    if(Save == 1)
    {
        Primes.push_back(List);
        i++;
    }
}

int ListPrimes()
{
    int FiveCount = 0;
    A = i;
    i = 0;
    while(i != A)
    {
        FiveCount++;
        cout << Primes.at(i++) << ",";
        if(FiveCount >= 5)
        {
            cout << endl;
            FiveCount = 0;
        }
    }
}

int main()
{
    cout << "\n\t::Prime Finder::\n"
         << "This program finds all the prime numbers\n"
         << "above zero and below the number you designate.\n"
         << "Your number: ";
    cin >> Number;
    cout << "Thank you; please wait as this could take awhile.\n";
    List = 1;
    i = 0;
    while(List <= Number)
    {
        List += 2;
        FindPrime();
    }
    ListPrimes();
    cout << endl;
    system("pause");
    return 0;
}

Note: This keeps counting even after it pulls a match; it only stops after it reaches 'Number' which, in part, slows it down. So if your number is '5000' it starts at 1 and counts up, so if the current number it is checking for primes is '4' it will keep counting beyond four until five thousand even if it knows four isn't a prime. Fourth project: (Finds each prime and posts it immiedently; faster but still too slow)
#include <iostream>
using namespace std;

unsigned long int List, Number, Counter, RiseNumber;
int FiveCount = 0;

int FindPrime()
{
    Counter = 1;
    bool Save = 1;
    while(Counter <= List)
    {
        Counter += 2;
        RiseNumber = 1;
        while(RiseNumber <= List)
        {
            RiseNumber++;
            if(List == (Counter * RiseNumber))
            {
                Save = 0;
                Counter = Number + 1;
            }
        }
    }
    if(Save == 1)
    {
        FiveCount++;
        cout << List << ",";
        if(FiveCount >= 5)
        {
            cout << endl;
            FiveCount = 0;
        }
    }
}

int main()
{
    cout << "\n\t::Prime Finder::\n"
         << "This program finds all the prime numbers\n"
         << "above zero and below the number you designate.\n"
         << "Your number: ";
    cin >> Number;
    List = 1;
    while(List <= Number)
    {
        List += 2;
        FindPrime();
    }
    cout << endl;
    system("pause");
    return 0;
}

Note: My best so far; please upgrade this one, and explain how it's updated. All in all, I think this was the perfect training experience for programming theory. I thought it would take me and hour or two tops, but it ended up taking six or seven spread through three days. I had to do much thinking and problem solving to get this far, and I am happy of my work. One last thing: I am quite sure there is some simple command that can be use to find primes; but using it wouldn't have givin me the training which I wanted from this project. Beyond that: insult/assault my code as far as you can and will. ~Servant~

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Servant of the Lord
My actual question here is: Using the fourth program(at the very bottom of the post) how would you upgrade it to perform faster?


Use a lookup table! :-)

Share this post


Link to post
Share on other sites
Quote:

Small Prime Finder can check about 180 million numbers per hour

Wow!
Mine would take several days to get that high if it could hold numbers that huge, which it can't.

However, anyone want to upgrade mine?

Share this post


Link to post
Share on other sites
This is the simplest algorythm to get prime numbers (I'm not implementing input/output functions, but I'm showing them just for the sake of doing it):


// Programming in C, so making my own bool type

enum bool { false = 0, true = 1 };

void read_max_number(int*);
void

int main()
{
int n,m,max,square;
bool prime;

read_max_number(&max);

// hardcode 2 to be prime:
print_prime(2);

// since 2 is the only even prime, look from 3 to up, skipping always 2
for(n = 3; n <= max; n += 2) {
// if there is no divisor until sqrt(n), then it is prime (number theory stuff)
square = (int)(sqrt(n));
prime = true;

if(square*square == n) {
prime = false;
}
else {
for(m = 3; m <= square; m += 2) {
if(n%m == 0) {
// not prime, so mark as non prime and break out of this loop
prime = false;

break;
}
}
}

if(prime) {
print_prime(m);
}
}

return 0;
}





You can also print your numbers in a file and check with the already printed ones to skip unecessary divisions.

Edit: I had done (x%m != 0) instead of (x&m == 0) ... corrected

[Edited by - Kalazart on March 15, 2006 8:09:49 PM]

Share this post


Link to post
Share on other sites
Have a look at a method called the Sieve of Eratosthenes (I think it is spelled right) If you google it, it can tell you the right spelling if mine is wrong.

Share this post


Link to post
Share on other sites
The Sieve of Eratosthenes is to find odd prime numbers. Works like this:

You mark all odd numbers until a given number. Then, one by one, starting from the lowest one (3), you go removing its multiples until the square root of the biggest number. Like this:

Create the list:
3 5 7 9 11 13 15 17 19 21 23 25 27 29

Remove multiples of 3
3 5 7 11 13 17 19 23 25 29

Remove multiples of 5
3 5 7 11 13 17 19 23 29

And there you go -- the above are all prime numbers, from 3 to 29. There are ways to optimize this, since you will always look for a number more than once (in this example, 15 is multiple of both 3 and 5 -- was to be removed twice, unecessarily), but I never even tried to create an algorythm for this Sieve.

Share this post


Link to post
Share on other sites
Quote:
Original post by Adam Hamilton
Have a look at a method called the Sieve of Eratosthenes (I think it is spelled right) If you google it, it can tell you the right spelling if mine is wrong.

You spelled it right.

Thats what I'm using in my code[smile]; although I got it from a book conveniently named "Stuff you should have learned in school" By Michael Powell

What the book said is what I tried to implement into my program. I think I got it right as my test run of the numbers between 0 and 50 only primes came out, which I checked on paper.

I am not truely interested on prime numbers(although it is an amazing topic) I am more interested on how to improve my programming skills. If anyone is willing to point out who I can optimize my programs I would be much obliged. Also, I am now moving onto my next project which is a better text adventure than my last; actauly involving monsters and such this time. [cool]

Thanks for the replies so far!

Share this post


Link to post
Share on other sites
Quote:
Original post by Kalazart
The Sieve of Eratosthenes is to find odd prime numbers. Works like this:

...but I never even tried to create an algorythm for this Sieve.


I'd never seen that algorithm before, and it looked pretty quick to run (as well as write) so I whipped this up.

Well, this ain't optimized by any means of the imagination, but it gets all primes in the first 100,000,000 (hundred million) natural numbers in about 8 seconds in release mode (VC++ 2005), not counting printing the numbers out, which would take well over a minute.

[edit] Removed the 100MB memory leak :-)


#include "stdafx.h"
#include "Math.h"
#include <iostream>

using namespace std;

void DoPrimes(unsigned iMax)
{
bool *pPrime = new bool[iMax+1];
pPrime[0] = false;
pPrime[1] = false;
pPrime[2] = true;
for(unsigned iSet = 3; iSet <= iMax; iSet++)
pPrime[iSet] = iSet%2?true:false; //Can't be prime if %2 is 0.

unsigned iRoot = (int)sqrtf((float)iMax);

for(unsigned iRemoveMultiples = 3; iRemoveMultiples <= iMax; iRemoveMultiples += 2)
{
if(!pPrime[iRemoveMultiples])
continue; //multiples already removed by a factor of iRemoveMultiples.

for(unsigned iRemove = iRemoveMultiples*2; iRemove <= iMax; iRemove += iRemoveMultiples)
pPrime[iRemove] = false;
}

/*for(unsigned iPrint = 0; iPrint <= iMax; iPrint++)
if(pPrime[iPrint])
cout << iPrint << '\n';*/

delete [] pPrime;
}

int _tmain(int argc, _TCHAR* argv[])
{
DoPrimes(100000000);


return 0;
}

Share this post


Link to post
Share on other sites
Here's a quick implementation of the sieve (as in I wrote it in a few minutes). Note that it also takes advantage of a few other factors to eliminate some cases. If finds the primes under 1000000 in under a second on my machine.


#include <iostream>
#include <deque>
#include <cmath>

void FindPrimes(std::deque<std::size_t>& primes, std::size_t upperBound) {
std::size_t current = 15;

while(current < upperBound) {
current += 2;

bool isPrime = true;
std::size_t mod6 = current % 6;

//Every prime number p > 3 has the form 6q + 1 or 6q + 5.
if(!(mod6 == 1 || mod6 == 5)) {
continue;
}

std::size_t maxVal = static_cast<std::size_t>(std::ceil(std::sqrt(static_cast<double>(current))));

for(int i = 0; primes <= maxVal; ++i) {
if(current % primes == 0) {
isPrime = false;
break;
}
}

if(isPrime) {
primes.push_back(current);
}
}
}

int main() {
std::size_t knownPrimes[6] = {2, 3, 5, 7, 11, 13}; //seed the list.
std::deque<std::size_t> primes(&knownPrimes[0], &knownPrimes[6]);
std::size_t upperBound;

std::cout<<"Please enter the upper bound: ";
std::cin>> upperBound;

FindPrimes(primes, upperBound);

std::copy(primes.begin(), primes.end(), std::ostream_iterator<std::size_t>(std::cout, "\n"));
}



Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!