Archived

This topic is now archived and is closed to further replies.

jcdenton999

Prime Number Program

Recommended Posts

I''m reading Bruce Eckel''s ''Thinking in C++'' book. I have no prior programming experience. After reading the chapter about loops, a question comes up which i can''t seem to find a solution to. The question is: "Write a program that uses two nested for loops and the modulus operator (%) to detect and print prime numbers (integral numbers that are not evenly divisible by any other numbers except for themselves and 1)". I am familier with the structure of for loops, and I know what the modulus operator does. Is there some sort of equation for detecting prime numbers that i can use. Thanks for any help

Share this post


Link to post
Share on other sites

for number in range
if number is divisible (x%y==0) by something except itself and one
it ain't prime
otherwise, print it cause it's prime

Not much to it, is there. ^_^

[edited by - twix on August 6, 2003 2:26:03 PM]

Share this post


Link to post
Share on other sites
*SPOILER*








an optimized version...


const int MAX_NUMBER=1000;
bool divisorFound=false;

for(int x=0, x<MAX_NUMBER, x+=2)
{

for(int y=3, y <= x/2, y+=2)
{
if (!(x%y)) { divisorFound=true; }
}
if (divisorFound) { std::cout << x; break;}
}


-Skips even number... only odd numbers can be prime
-Stop looking for other value of y when y>=x/2... x cannot be divided by a number more than its half. (It''s technically square root but i didn''t bother..)
-Breaks immediately when a divisor is found.

Share this post


Link to post
Share on other sites
Another optimization is that you don''t need to even test every odd number, only the previously found prime numbers. Save that until you get to lists and things though.

Share this post


Link to post
Share on other sites
Isn't a number a prime when there are no divisors? And shouldn't you reset the variable after each search?!
And if a divisor is found, the number is surely not a prime, so you can step out of the for-loop.
Starting the first loop from 0 isn't a good idea when you add 2 to that number every time, because that makes you checking only pair numbers. My code isn't correct yet , it still has a bug in it.


#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

int main(int argc, char *argv[])
{
const int MAX_NUMBER=1000;
bool divisorFound=false;
for (int x=1; x<MAX_NUMBER; x+=2)
{
for (int y=3; y <= sqrt((double)x); y+=2)
{
if (x%y)
{
divisorFound=true;
break;
}
}
if (divisorFound)
{
cout << x << endl;
} else {
divisorFound = false;
}
}
system("PAUSE");
return 0;
}


"My basic needs in life are food, love and a C++ compiler"
[Project AlterNova] [Novanet]



[edited by - Vich on August 6, 2003 4:10:53 PM]

Share this post


Link to post
Share on other sites
Yeah some mistakes I did that quickly... but still.. the guys learning so obscure constructs like the ? operator and the use of bitshifts should be avoided.

Share this post


Link to post
Share on other sites
Also, you only need to test up to sqrt(x), not x/2.

Whoops, you metioned that already.

[edited by - twix on August 6, 2003 4:09:25 PM]

Share this post


Link to post
Share on other sites
I'm addicted to making these pointless little programs. Something must be seriously wrong with me.

#include <iostream>
#include <algorithm>
#include <list>
#include <cstdlib>
#include <boost/lambda/lambda.hpp>

using namespace std;
using namespace boost::lambda;

int main()
{
const int MAX_NUMBER = 1000;
list<int> primes;
cout << 2 << endl;

for (int x=3; x<MAX_NUMBER; x+=2)
if (find_if(primes.begin(), primes.end(), x%_1==0) == primes.end())
primes.push_back(x);

for_each(primes.begin(), primes.end(), cout << _1 << "\n");

system("PAUSE");
return 0;
}

Still, mine pwnz and you know it.

[edited by - twix on August 6, 2003 4:43:07 PM]

Share this post


Link to post
Share on other sites

typedef unsigned long ulong;
bool isPrime(ulong n)
{
if (n == 2)
return true;
if ( (n != 2) && (n % 2 == 0) || (n % 5 == 0))
return false;
for (ulong x = 3; (x * x) < n; x +=2)
{
switch(n % x)
{
case 0:return false;
}
}
return true;
}

i think this is the currently known fastest algorithm for such a program. probably could use some _asm_ optimizations but it works wonders on even a measliy 233 mhz machine, and probably will find you any prime number you need on a 2.4 ghz.

Share this post


Link to post
Share on other sites
quote:
Original post by vaneger
i think this is the currently known fastest algorithm for such a program. probably could use some _asm_ optimizations but it works wonders on even a measliy 233 mhz machine, and probably will find you any prime number you need on a 2.4 ghz.


You sure that''s the right algorithim? It doesn''t seem to work. Say n is 9, When it gets to the for loop you''re going to have 9 < 9, which is false so loop doesn''t execute and it returns true.





--{You fight like a dairy farmer!}

Share this post


Link to post
Share on other sites

typedef unsigned long ulong;
bool isPrime(ulong n)
{
if ( (n != 2) && (n % 2 == 0) || (n % 5 == 0))
return false;
for (ulong x = 3; (x < (n/2)); x +=2)
{
switch(n % x)
{
case 0:return false;
}
}
return true;
}

yes you are correct it didnt work 100%, the numbers that are squares of primes made it work incorrectly, the above code works the right way.

Share this post


Link to post
Share on other sites

#include<math.h>
typedef unsigned long ulong;
bool isPrime(ulong n)
{
if ( (n != 2) && (n % 2 == 0) || (n % 5 == 0))
return false;
for (ulong x = 3; (x <= sqrt(n)); x +=2)
{
switch(n % x)
{
case 0:return false;
}
}
return true;
}
bool checkPrime(ulong n)
{
if ( (n != 2) && (n % 2 == 0) || (n % 5 == 0))
return false;
ulong x;
for (x = 3; (x*x <= n/2 ); x +=2)
{
switch(n % x)
{
case 0:return false;
}
}
return true;
}


ok checkPrime doesnt work correctly it will have 28 primes in 100 compared to the actual 25,197 in 1000 instead of 167. isPrime computes the primes correctly. the odd thing is checkPrime runs about 4 times faster than isPrime. if we can figure out how to minimize the errors of checkPrime we might be able to cut our program time in 4. (checkPrime was running at about .032 milliseconds for 50 calls while isPrime was running at about 1.23 milliseconds for 50 calls) or we cna deal with the percent error as is and have a imperfect but faster function.

[edited by - vaneger on August 6, 2003 8:46:57 PM]

Share this post


Link to post
Share on other sites
so any one know how i cna figure out if the error checkPrime has is regular or not( like if it accidently says number g is prime when its not) so that i might be albe to catch the problem and remove it (like if every g numbers gives an error i can keep a counter and set it to false if teh counter is = g);

Share this post


Link to post
Share on other sites
This seems pretty fast:
#include<list>
#include<math.h>
#include<iostream.h>

using namespace std;

void main(void)
{
list<int> primes;
list<int>::iterator itor;
list<float> invprimes;
list<float>::iterator invitor;
int num;
int maxnum = 100000;
float sqrtnum = 0;
int isnotprime = 0;
primes.push_back(2);
invprimes.push_back(0.5f);
for(num = 3; num < maxnum; ++++num)
{
sqrtnum = sqrt(num);
invitor = invprimes.begin();
for(itor = primes.begin(); *itor < sqrtnum && !isnotprime && itor != primes.end(); ++itor)
{
if(num * *invitor == num / *itor)
isnotprime = 1;
++invitor;
}
if(isnotprime == 0)
{
primes.push_back(num);
invprimes.push_back(1.0/num);
// cout << num << "\n";

}
isnotprime = 0;
}
/* for(itor = primes.begin(); itor != primes.end(); ++itor)
{
cout << *itor << "\n";
}*/

}


I'm sure there are optimizations to be made I'm very tired right now... seems pretty darn fast though... Not the same as the other function in that it doesn't tell you if one specific number is prime, but gets the full list pretty fast... I would try using a static array for the data to see how this improoved speed, but as I said I'm tired and I need some rest... maybe tommarow at work I'll make it a little faster...

Dwiel

For all in need of free hosting for pics/etc:
upload to ftp location: dwiel.no-ip.com user/pass = FreeHostedPics/gamedev
Your files will be available on the inet immediately at http://dwiel.no-ip.com/~FreeHostedPics/
Feel Free to create a folder there for your self!


[edited by - Tazzel3d on August 6, 2003 11:30:48 PM]

Share this post


Link to post
Share on other sites
well im not looking to making a list of the primes until after this function is optimized, but you coudld just use a for loop and call the function rather than use an array and a for loop to fill it in place.thus the function can also be used to find primality of a given number N, which is the purpose, also later im going to use it fora speed test on differnt computers.

Share this post


Link to post
Share on other sites
This only explicitly uses one for loop, but I''d expect slice_array assignment to be implemented using a second one.

#include <cstdlib>
#include <iostream>
#include <valarray>

using namespace std;

const int MAX_NUMBER = 1000;


int main()
{
valarray<bool> varr(true, MAX_NUMBER);

for (int x = 2; x < MAX_NUMBER; ++x)
{
if (varr[x])
{
cout << x << endl;
varr[slice(x, MAX_NUMBER / x, x)] = false;
}
}
}

Share this post


Link to post
Share on other sites
Crazy old school skillz kinda....
Whatever. BTW, as the number of primes grows so does how long the test takes.(bummer)

Nice code Beerhunter!


#include <stdio.h>
#include <conio.h>

// ooh so slow

//#define NUM_RANGE 100000000

//#define MAX_PRIMES 5761455


// seems pretty quick

#define NUM_RANGE 104729 // first ten thousand primes

#define MAX_PRIMES 10000

unsigned long int primes[MAX_PRIMES];


int main(void)
{
unsigned long int i,j,square_root,prime_squared,toggle_adder,primes_found;

// Intro

printf("Primes from 2 to %d.\n",NUM_RANGE);

// put the first three known primes in the list

primes[0]=2;primes[1]=3;primes[2]=5;
primes_found=3;

// generate the primes

prime_squared = primes[2] * primes[2];
square_root = 2;
toggle_adder = 2;
for(i=7; i<=NUM_RANGE; i+=toggle_adder)
{

// when the numbers become greater than the currently used squared prime use the next

if(prime_squared<i)
{square_root++;
prime_squared = primes[square_root] * primes[square_root];
if(square_root>400){printf(".");} // progress dots so it looks cool

}

// using the square of the primes to limit the tested primes

// j=2; no need to divide by 2 or 3 because their composites are skipped

for(j=2; (j<=square_root)&&(i%primes[j]); j++){}

// Check if prime was found

// basically if j > square_root then the number couldn't be divided by the primes

if(j>square_root)
{if(primes_found<=MAX_PRIMES){primes[primes_found++] = i;}
else{primes_found--;printf("\n*** Reached Max Primes ***\n");break;}
}

toggle_adder = 6 - toggle_adder;
}

// Display results

printf("\n\nResults\n--------\n");
printf(" %u Primes found.\n Largest prime used to factor was %u. The %uth prime found.\n",primes_found,primes[square_root],square_root+1);
printf("\n");

// End of Primes

return(0);
}


Well there are two for loops.

[edit]
fixed prime list limit check to exit loop once it is full

[edited by - CodeJunkie on August 8, 2003 1:26:05 AM]

Share this post


Link to post
Share on other sites

#include<math.h>
typedef unsigned long ulong;
bool isPrime(ulong n)
{
if ( (n != 2) && (n % 2 == 0) || (n % 5 == 0))
return false;
for (ulong x = 3; (x <= sqrt(n)); x +=2)
{
switch(n % x)
{
case 0:return false;
}
}
return true;
}
bool checkPrime(ulong n)
{
if ( (n != 2) && (n % 2 == 0) || (n % 5 == 0) )
return false;
ulong x;
for (x = 3; ((x*x)/2 <= n/2 ); x +=2)
{
switch(n % x)
{
case 0:return false;
}
}
return true;
}

i fixed it and now checkPrime is faster than isPrime and its correct

Share this post


Link to post
Share on other sites
i got a VB .net version here
uploaded to http://www.mynetcologne.de/~nc-loerscma/PB.zip if u wanna check it. got 3 small bugs, but nothing important


global
Dim Stop_The_Loop As Boolean
Dim Weiter As Boolean


button start
If btnStart.Text = "Start" Then
btnStart.Text = "Stop"

Dim Zahl As Double
Dim Zähler As Double
Dim Wurzel As Double
Dim Einer As Integer

Stop_The_Loop = False
first get next number
If Not (IsNumeric(tbAnfangsZahl.Text)) Then MsgBox("AnfangsZahl is wrong") : Exit Sub
If Int(tbAnfangsZahl.Text) < 9 Then MsgBox("AnfangsZahl is smaller than 9") : Exit Sub

Zahl = tbAnfangsZahl.Text
lbAktuelleZahl.Text = Zahl - 1
Do
Zahl = Int(lbAktuelleZahl.Text) + 1
lbAktuelleZahl.Text = Zahl
Wurzel = Int(Math.Sqrt(Zahl))
pbTeiler.Minimum = 3
pbTeiler.Maximum = Wurzel + 1
pbTeiler.Value = 3
Einer = Int(Microsoft.VisualBasic.Right(Str(Zahl), 1))
Do
Weiter = False
If (Einer <> 1) And (Einer <> 3) And (Einer <> 7) And (Einer <> 9) Then
Weiter = True
Exit Do
End If
Zähler = 1
Do
Zähler += 2
If Zahl Mod Zähler = 0 Then
Weiter = True
Exit Do
End If
If Zähler Mod 51 Then
pbTeiler.Value = Zähler
System.Windows.Forms.Application.DoEvents()
End If
Loop Until Zähler >= Wurzel
Exit Do
Loop
If Not (Weiter) Then
tbPrimzahlen.AppendText(":" + Trim(Str(Int(Zahl))))
Text = Trim(Str(Zahl))
End If
Loop Until Stop_The_Loop
tbAnfangsZahl.Text = lbAktuelleZahl.Text
Else
btnStart.Text = "Start"
Stop_The_Loop = True
End If
End Sub



ok, code wont be so interesting 4 u, but maybe program helps u to check if u get real prime numbers

[edited by - Amegon on August 7, 2003 11:15:43 PM]

[edited by - Amegon on August 7, 2003 11:16:44 PM]

Share this post


Link to post
Share on other sites
umm my functions do get real prime numbers, but the formula i used in the checkPrime didnt work 100% correctly it was getting more primes than it should because i didnt divide by x*x by 2. the code as is runs with checkPrime being 3 to 4 times faster than isPrime, but i later modified it to do the sqrt outside fo the loop and now isPrime runs about 1.3 times faster than checkPrime.

Share this post


Link to post
Share on other sites