Sign in to follow this  
Servant of the Lord

Finding Prime Numbers

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
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
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[i] <= maxVal; ++i) {
if(current % primes[i] == 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
A good way toward becoming better at algorithm design is to look at the time and space complexity of each algorithm. For more info on that go to any site on Complexity Theory (like this one).

The Sieve of Erastosthenes is a very fast way to find primes, but as you can see from your implementation, it's extremely memory intensive. For each number up to sqrt(n) it does a pass through the list marking n/sqrt(n) elements, so it is an O(n) algorithm, which is very fast, but it also requires O(n) memory, which can get pretty overwhelming when finding large primes.

The other really common method is to check for divisibility of a number for all integers up to and including the floor of it's square root. This is quite clearly slower, doing at worst sqrt(n) divisibility checks for n numbers, so it's an O(n*sqrt(n)) algorithm, but it has an O(1) memory requirement (namely it doesn't actually use any memory).

I had just concocted the idea of using a list of primes as the set of numbers to check for divisibility. So you would make a list of the primes as you go along, and then to check if a number n is prime, you would check for divisibility against all of the primes up to n (since any composite number can be decomposed to its prime factors). This seems like it should be faster, right? I thought it was, but then I looked into it and discovered that it really isn't. The number of primes up to a number n is approximated at n/log(n), so finding all of the primes up to a number n would be an O(n^2/log(n)) operation, which is definitely worse than O(n*sqrt(n)) and has a space complexity of O(n/log(n)).

But, after thinking about it, I realized that you could further optimize by only checking for divisibility by known primes up to and including the floor of the square root of n. This works because all natural numbers can be decomposed to their prime factors. Indeed, unless you screwed up majorly, you should never hit a scenario where you determine a number is composite when you check if it's divisible by 6 since you should have caught it with 2 or 3. This means that the complexity for determining if a number n is prime would be approximately O(sqrt(n)/log(sqrt(n))), which is indeed less than sqrt(n). I don't know for certain if this would decrease the complexity by a given order, but it would practically be a decent bit faster in larger values of n (consider n=10^100; sqrt(n) = 10^50, log(sqrt(n)) = 50, assuming base 10 logarithms, so it would take at worst 1/50th as many checks to determine if a number around 10^100 is prime than the square root method). So this is indeed faster... but it does have a large memory footprint as well at O(n/log(n)), so if n=10^100, you'd need about 10^100/log(10^100) = 10^98 elements in your list of primes. This is still less than if you'd used the Sieve though. You could also save yourself a bit of time by never checking even numbers, though that will not reduce your actual complexity at all, it'll just reduce your n to n/2.

What's my point in all that? It's that to become better at designing algorithms, and hence at programming, you have to consider time and space complexity of what you write (the big-O notation used above is the most common metric for this, but you don't have to use it if you don't want). And so, having seen these, it's up to you to decide what is best for you. The Sieve is fastest but requires the most memory. Checking against all numbers up to the square root for divisibility is slower, but requires no memory. Keeping that list of primes is somewhere in between the two. And this is where you have to analyze your requirements to determine which method is best for the situation. Some algorithms will run faster if you give them some memory to work with, but if it becomes too much memory, it might not be worth the speed gains you get. Other things in this case to consider are whether you want all of the primes up to a number, or just to determine if a given number is prime. If you just need to know if a given number is prime, then check for divisibility up to the square root, since it's only O(sqrt(n)) and needs no memory, whereas the other methods require memory and would be slower since they'd have to find a bunch of other primes in the process.

Hope my long-winded, rambly it's-2am-and-I-should-be-in-bed discussion on this has helped you out somewhat :)

-Auron

Share this post


Link to post
Share on other sites
Quote:
Original post by Servant of the Lord
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.

The Craftsman

Read it! [smile] It's about test driven development/unit testing and it starts out with someone trying to create a prime generator. It's not really about writing highly optimized code, but rather it shows you a way to write clean, readable and bug free code in less time. It's a common practice in business btw.

Share this post


Link to post
Share on other sites
Heres my implementation of a prime number generator,

Note that I borrowed a small snippett of code from Washu's post to save me the effort (hope you dont mind) but the actual algorithm itself is different (I dont know if it already exists.. I just made it up [smile] but it seems to be pretty fast)


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

bool div_by_prime(std::size_t val, const std::deque<std::size_t>& primes)
{
std::size_t maxVal = static_cast<std::size_t>(std::ceil(std::sqrt(static_cast<double>(val))));

for(unsigned int i = 0; primes[i] <= maxVal; ++i)
{
if(val % primes[i] == 0)
return true;
}
return false;
}

void find_primes(std::size_t finish)
{
const int inc[11] = {1, 2, 2,
4, 2, 4, 2, 4, 6, 2, 6};

unsigned int i = 0;
std::size_t val = 2; //First prime

std::deque<std::size_t> primes;

while (val <= finish)
{
if (val < 11 || !div_by_prime(val, primes))
primes.push_back(val);

val += inc[i];

if(i == 10)
i = 3;
else
++i;
}

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

int main()
{
find_primes(10000);

std::cin.get();
return 0;
}

Share this post


Link to post
Share on other sites
While we're at it, I figured I'd throw in my two cents :).

Here is a sieve implementation I wrote a while back that is pretty fast, it calculates all the primes up to 10 million in less than a second on my machine. This code is not big endian safe.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

const int MAXNUM=10000000;
unsigned int sieve[MAXNUM/64 + 2];

void calcSieve() {
for (int i=0; i<sizeof(sieve)>>2; i+=3) {
sieve[i] = 0x6DB6DB6D;
sieve[i+1] = 0xDB6DB6DB;
sieve[i+2] = 0xB6DB6DB6;
}
sieve[0] |= 6;

for (int i=2; 4*(i*i+i)+1<=MAXNUM; i++) {
if (sieve[i>>5]&(1<<(i&31))) {
int factor = (i<<1)+1;
for (int j=factor+i; j<(MAXNUM/2)+1; j+=factor) {
sieve[j>>5] &= ~(1<<(j&31));
}
}
}
}

bool isPrime(int num) {
if (!(num&1) && num!=2) return false;
num >>= 1;
if (sieve[num>>5]&(1<<(num&31))) return true;
return false;
}

bool isPrimeSlow(int num) {
for (int i = 2; i*i <= num; i++)
if (num % i == 0) return false;
return true;
}

int main() {
calcSieve();

//printf("Incorrect results:\n");
//for (int i = 1; i <= MAXNUM; i++)
// if (isPrime(i) != isPrimeSlow(i)) printf("%d, ", i);
//printf("\n");
printf("Primes less than 100:\n");
for (int i = 1; i <= 100; i++)
if (isPrime(i)) printf("%d, ",i);
printf("\n");
}


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this