11 replies to this topic

[Csshih]

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 prototypes
void 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: none
void 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: none
void 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 numbers
void 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
I'm using Visual C++ 6.0.
Thanks,
Craig

Edited by Csshih, 14 February 2008 - 06:42 PM.

[BuffaloHelp]

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 999

temp = X

//start loop
//set COUNTER = 0
//set REMAINER = 0
//set temp = 0

while temp is NOT equal to 0
REMAINDER = X / temp
IF REMAINDER is a whole number, COUNTER = COUNTER + 1
IF COUNTER is grater than 2, then it's NOT PRIME
ELSE IF COUNTER is equal to 2, then IS PRIME save X to ARRAY
ELSE temp = temp - 1

//exit loop

X = X + 1 and X is not grater than 999

//go back to loop for checking PRIME

Oooohhh... 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]

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]

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 could
just 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 calling
a function only once, makes reading easier. Other than that, seems like nice code.

[Csshih]

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]

Quote

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]

Csshih, on Dec 18 2007, 11:11 AM, said:

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.

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]

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

-reply by Keertana

[iGuest]

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]

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