• ### Announcements

#### Archived

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

# Prime Number Program

## Recommended Posts

jcdenton999    122
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 on other sites
twix    636
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 on other sites
jfclavette    1058
*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 on other sites
Raloth    379
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 on other sites
Vich    142
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 on other sites
jfclavette    1058
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 on other sites
twix    636
Also, you only need to test up to sqrt(x), not x/2.

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

##### Share on other sites
twix    636
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 on other sites
Oluseyi    2103
quote:
Original post by twix
Still, mine pwnz and you know it.
Uh, no.

Sieve of Eratosthenes

##### Share on other sites
twix    636
Feh, I''m just implementing people''s suggestions here.

##### Share on other sites
Vich    142
quote:
Original post by Oluseyi
quote:
Original post by twix
Still, mine pwnz and you know it.
Uh, no.

Sieve of Eratosthenes

I second that.

##### Share on other sites
vaneger    100
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 on other sites
Greatwolf    125
quote:
Original post by Vich
quote:
Original post by Oluseyi
quote:
Original post by twix
Still, mine pwnz and you know it.
Uh, no.

Sieve of Eratosthenes

I second that.

I third that.

--{You fight like a dairy farmer!}

##### Share on other sites
Greatwolf    125
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 on other sites
vaneger    100
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 on other sites
vaneger    100
#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 on other sites
vaneger    100
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 on other sites
vaneger    100
bump so thsi doesnt get buried in old posts

##### Share on other sites
Dwiel    365
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 on other sites
vaneger    100
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 on other sites
Beer Hunter    712
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 on other sites
CodeJunkie    144
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.

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

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

##### Share on other sites
vaneger    100
#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 on other sites
Amegon    122
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 Booleanbutton 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ählerSystem.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]