Most Efficient Code To Get Prime Numbers

[Csshih 0]

Can anyone write a more efficient code than this to get the prime numbers from 1 -999?

// Assignment: sieve.cpp// Purpose: To write the most efficient program//			that outputs prime numbers.#include<iostream.h>#include<iomanip.h>#include<math.h>// declare constant MAX_NUMBER to be the # of arrays.const MAX_NUMBER = 1000;// declare array primes.bool primes[MAX_NUMBER];// function prototypesvoid initializeArray();void findMultiples();void printSubscripts();int main(){	// call to functions	initializeArray();	findMultiples();	printSubscripts();	return 0;}//*****************************************************// function initializeArray//// Purpose: to initialize the Aray//// Input: none// Output: nonevoid initializeArray(){	// start from index 2, ignoring 1 and 0	for(int index = 0; index < MAX_NUMBER; index++)		primes[index] = true;		primes[0] = false;		primes[1] = false;}//*****************************************************// function findMultiples//// Purpose: assign false to multiples of prime numbers//// Input: none// Output: nonevoid findMultiples(){	int steps = 0;	// for loop, starting the primes at 2, incrementing every loop	for(int index = 2; index < sqrt(MAX_NUMBER); index++)		// if true, then continue		if(primes[index] == true)			// all multiples of primes are assigned false			for(int multiplier = 2; multiplier * index < MAX_NUMBER; multiplier++)			{										primes[multiplier * index] = false;				steps++;			}	cout << "Number of steps are : " << steps << endl;}//*****************************************************// function printSubscripts//// Purpose: print prime numbers to console//// Input: none// Output: prime numbersvoid printSubscripts(){	cout << "The prime numbers from 1 to " << MAX_NUMBER-1 << " are:\n" << endl;	// output primes starting from primes[2]	for(int index = 0; index < MAX_NUMBER; index++)	{		if(primes[index])			// a "tab" between every prime number.			cout << index << "\t";	}	cout << endl;}

Some of the comments may not be correct because I'm just learning programming :PI'm using Visual C++ 6.0.Thanks,Craig

Edited February 14, 2008 by Csshih (see edit history)

[BuffaloHelp 24]

I haven't programmed in C++ in years, but the above program doesn't look complete. Are you sure the above code produces all prime numbers?I would imagine you have to double check to see if the number selected between the range is TRUE prime. The best example I can think of is to start dividing a number and work its way down to see the remainder is a whole number. If there are multiple remainders that result in whole numbers, it's not prime.Such that,X = a number between 1 and 999temp = X//start loop//set COUNTER = 0//set REMAINER = 0//set temp = 0while temp is NOT equal to 0REMAINDER = X / tempIF REMAINDER is a whole number, COUNTER = COUNTER + 1IF COUNTER is grater than 2, then it's NOT PRIMEELSE IF COUNTER is equal to 2, then IS PRIME save X to ARRAYELSE temp = temp - 1//exit loopX = X + 1 and X is not grater than 999//go back to loop for checking PRIMEOooohhh... my fuzzy logic looks alright but I'm sure someone will find a flaw in it. Until then you get my point of view. Basically you are picking a number between 1 and 999. Start dividing a chosen number by numbers preceding to the chosen number. If a chosen number is divisible by other numbers (more than twice, itself and 1 which is kept at record by COUNTER) than it is NOT a prime number. And keep on going until X is equal to 999.

[Csshih 0]

When my code gets a prime number, it already removes all multiples of it.I think that should be complete though.I compared the output to a online list of primes, it was correct.

[osknockout 0]

A simple idea. Replace your index++'s with index += 2 since there is no other even prime number other than 2.You're going to have to readjust your code a bit, but it should be worth the ~50% performance increase. Same thing with your boolean array you don't need to account for any even value besides two, so you couldjust have a boolean variable for 2 (or nothing, really) and just have a boolean array for odd number tests.-Btw, it's generally a good thing if you keep short code in main if you can - particularly if you're only callinga function only once, makes reading easier. Other than that, seems like nice code.

[Csshih 0]

Nice Idea with the index +=2, that should reduce the number of steps by 1/2.Thanks!and about the functions,my teacher said that I have to have only calls to functions in main. >.<

[osknockout 0]

my teacher said that I have to have only calls to functions in main. >.<

Bah! Teachers... I'm so glad I learned C myself.I for one completely disregard that rule.

You know, looking at the code again, I think if you increased your range
to say 1 to a billion, your technique would not be the most efficient anymore,
but it's the best I can think of right now for low ranges.

[larryf 0]

Can anyone write a more effecient code than this to get the prime numbers from 1 -999?

Here is an algorithm I wrote using the Rabin/Miller test to test for prime numbers. I even commented it years ago. This is the best way to test for primes, and it will give you all the primes up to MAXINT.

n - 1 = 2km for some k > 0 and odd integer m.
a = 1 < a < n - 1
We say that n passes the Rabin-Miller test for the base a if
either the first term in this sequence is 1, or 1 occurs later
in this sequence and is immediately preceded by -1. If the test
fails, we know that n is composite, and describe the base a as
a witness to the compositeness of n. The crucial extra information
we can derive is that if (odd) n is composite, then at least 3/4
of the numbers a with 1 < a < n - 1 are witness to this fact.
First calculate m, in C++ we do this by simply shifting the bits
right k times, until m is odd and less than n.
Next, we calculate a, such that a is less than n - 1, and a > 1.
Then, we calculate a ^ m mod n. If this result is 1, then
we need to generate a new a and try again. After iIterations, we
can say that n is prime with 1/1024 margin of error.

Two function prototype follow, one for 32 bit integers, one for
multi-precision integers.
*/

int RabinMiller(UINT4 n, int iIterations)
{
srand(100);
int isprime = 0;
UINT4 m = n - 1;
UINT4 k = 0;
UINT4 a = 0;
if((n & 1) == 0) {
return 0;
}
if(m > 0) {
while((m & 1) == 0)
{
k++;
m = (m >> 1);
}
}
GetRandomA(&a, n);
UINT4 r;
do
{
r = 1;
for (int i = 0; i < m; i++)
{
r = (r * a) % n;
}
if(r == 1 || r == (n - 1)) {
GetRandomA(&a, n);
isprime = 1;
continue;
}
for(UINT4 x = 0;x < k + 1;x++)
{
r = (r*r) % n;
if(r == (n - 1)) {
isprime = 1;
break;
}
}
if(isprime == 0) {
break;
}
GetRandomA(&a, n);
}
while(iIterations--);
return isprime;
} linenums:0'>typedef unsigned int UINT4;void GetRandomA(UINT4 *a, UINT4 n){ *a = rand() % (n - 2) + 1;}/* Rabin/Miller test to test a prime number. Taken from Larry Frieson's Password Manager. n - 1 = 2km for some k > 0 and odd integer m. a = 1 < a < n - 1 We say that n passes the Rabin-Miller test for the base a if either the first term in this sequence is 1, or 1 occurs later in this sequence and is immediately preceded by -1. If the test fails, we know that n is composite, and describe the base a as a witness to the compositeness of n. The crucial extra information we can derive is that if (odd) n is composite, then at least 3/4 of the numbers a with 1 < a < n - 1 are witness to this fact. First calculate m, in C++ we do this by simply shifting the bits right k times, until m is odd and less than n. Next, we calculate a, such that a is less than n - 1, and a > 1. Then, we calculate a ^ m mod n. If this result is 1, then we need to generate a new a and try again. After iIterations, we can say that n is prime with 1/1024 margin of error. Two function prototype follow, one for 32 bit integers, one for multi-precision integers.*/int RabinMiller(UINT4 n, int iIterations){ srand(100); int isprime = 0; UINT4 m = n - 1; UINT4 k = 0; UINT4 a = 0; if((n & 1) == 0) { return 0; } if(m > 0) { while((m & 1) == 0) { k++; m = (m >> 1); } } GetRandomA(&a, n); UINT4 r; do { r = 1; for (int i = 0; i < m; i++) { r = (r * a) % n; } if(r == 1 || r == (n - 1)) { GetRandomA(&a, n); isprime = 1; continue; } for(UINT4 x = 0;x < k + 1;x++) { r = (r*r) % n; if(r == (n - 1)) { isprime = 1; break; } } if(isprime == 0) { break; } GetRandomA(&a, n); } while(iIterations--); return isprime;}
To call the code, you can do it in a loop.

for(int x = 0;x < 9999;x++){  int isPrime = RabinMiller(x, 5);}

If the return value is non-zero, then the number is prime. And you don't have to worry about skipping even numbers, etc, because the algorithm does it for you.

I used the MPC version of the algorithm (which I left out, because you don't need primes over 32 bit) in a cryptographically secure application with no problems at all.

There is also a Fermat test you can do, which seems a lot like the code you listed...

Larry

[iGuest 3]

Has anyone heard of the AKS algorithm that runs in O(and) time.-reply by Keertana

[iGuest 3]

Code 4 prime nos. in CMost Efficient Code To Get Prime Numbers// prime nos. B/w m and and#include<stdio.H>Char prime(int x)/*********************************************************************************************************************************************************************Function testing nos. Individually*********************************************************************************************************************************************************************/{ int I; if(x==1) return 'and'; int t=0; if(x==2) return 'Y'; for( I=2; I<=x/2+1; I++) {  if(x%I==0)  {  t++;  } } if(t==0) return 'Y'; //Test +ve// else return 'and';  //Test -ve//}/*******************************************************************************Main function*/Void main(){  int k=0, m, and, I;  char t;  printf("Enter the nos. B/w which you want to find prime nos.");  scanf("%d %d", &m, &and);  for( I=m; I<=and; I++)  {   t = prime(I);  if(t=='Y')  {  printf("and%d", I);  k=k+1;  }  }  printf("nTotal prime no. Is %d",k);}-reply by Sarvpriye

 

[iGuest 3]

prime numbersMost Efficient Code To Get Prime Numbers

I want to get all the prime numbers in a given number by the user then I want to get the sum of all the prime numbers is there any one who can help me out

-reply by louie

[iGuest 3]

I am so grateful for this site,at least I managed to get an idea of geting primes,as a programmer(beginner) I want to learn how to read and write to files,I do understand that the type of file is determined by the extension on it.For example,files with extension'.Txt' are text files,'.Doc' are word files etc

I want to write a C program that will be able to ceive the different types of numbers and write them in appropiate files.I want to start by using 3 files,file_even for word document,file_odd for text doc and file_prime for an excel file. If I use integersf rom 1 to 250,and write all even files with their halves in file_even so that the every even number is on its own line and a number is separated from its half with a tab,write all odd numberswith  theirs squares in file_odd so that every odd number is on its own line and is separated from its square with a tab,also write all prime numbers and their thirds(rounded to 2 decimal places) in  file_prime and every prime number is on its own lineand a prime number and its third in separate cells(equivalent of of tabs) I wrote a certain code but I want to compare oor even make it better,some help,thanks

-Dense

[iikwalsemsiskweyrd 0]

#include <iostream>#include <cmath>using namespace std;bool isPrime( int i );int main(){	for( size_t i = 1; i < 1000; i++ )	{		if( isPrime( i ) )		{			cout<<i<<endl;		}	}	system( "pause" );	return 0;}bool isPrime( int num ){	int limit = sqrt( static_cast<double>(num) );	if ( num == 2 )	{		return true;	}	if ( num == 1 || num % 2 == 0 )	{		return false;	}	for( size_t i = 3; i <= limit; i += 2 )	{		if( num % i == 0 )		{			return false;		}	}	return true;}

*system( "pause") was placed for the MSVS console not to automatically close. *newline at the end of the file if you are compiling with GCC.

Edited June 3, 2010 by iikwalsemsiskweyrd (see edit history)