Prime Number Generator

[lalhsboard 0]

I've been interested in learning C++ lately. I used to program in BASIC, but I've recently decided that I would begin to learn a more challenging language. I read online tutorials, and bought a book. Using only very basic C++, I wrote a one-file program that generates higher and higher prime numbers. I was always interested in how high prime numbers would get before they became very scarce.

My program tries to generate prime numbers with maximum efficiency. It uses test division on a constantly increasing integer to determine if it is prime or not, and spits out the ones that test to be truly prime. It only tests odd numbers, and therefore only has to test divide by odd numbers. It also numbers the primes. I'll post the source here. Any feedback is appreciated, but remember: I'm just a beginner.

#include <iostream>int testForPrime (int n) {	int p, i;	p = 1;	i = 3;	int result = n;	while (i < result) {		result = n / i;		if (n == i * result) {			p = 0;			i = n;		}		i = i + 2;	}	return (p);}int main (int argc, char * const argv[]) {	int p, i, n;	i = 3;	n = 5;	std::cout << "Initiating prime number generation sequence...\n\n1: 2\n2: 3\n";	while (1) {		p = testForPrime (n);		if (p == 1) {			std::cout << i << ": " << n << "\n";			i++;		}		n = n + 2;	}	return 0;}

Edited March 23, 2006 by lalhsboard (see edit history)

[vizskywalker 0]

I see http://forums.xisto.com/style_images/1/folder_rte_images/rte_dots.gif
http://forums.xisto.com/no_longer_exists/ only a few problems code wise with your program. The first is the type that you defined your testForPrime() function to be. Since it only returns a 1 or a zero it is essentially functioning as a boolean function, so I would define it as such. Then, you would define p to true and adjust it to false. This would simplify your if statements when you check if something is prime. You could also embed a return statement into the if statement that checks for perfect divisions to prevent the whole while loop from running and dcrease clutter. Also, you defined a while loop with one as the value, which although works, would be better defined as while(true). Also, it is general good programming practice to not code infinite loops, so I would recommend adding an exit prompt to the while statement, but that is merely a choice I would make. I would also deifne the variables that have specific meanings to words or abbreviations with meaning to help you remember what they are if you ever go back to modify this code or include it in a later program. So the revisions I have for your code would look like this:

#include <iostream>bool TestForPrime (int value) {   int testvalue = 3;   result = value;   while (testvalue < value) {	  result = value / testvalue;	  if (value == testvalue * result) {		 return false;	  }	  testvalue += 2;   }   return true;}int main (int argc, char * const argv[]) {   int count = 3;   int value = 5;   std::cout << "Initiating prine number generation sequence...\n\n1: 2\n2: 3\n";   while (true) {	  if (testForPrime(n)) {		 std::cout << count << ": " << value << "\n";		 count++;	  }	  value += 2;   }   return 0;}

Just to let you know hoever, the algorithm you are using is by far not the most efficient algorithm for finding prime numbers, and most of the efficient ones are extremely complex. If you are really interested in looking at when prime numbers become scarce, you may be interested in the Zeta function and the associated millenium problem.

~Viz

[iGuest 3]

Dude...The loop won't stop. Try getting the input from the user and then going up to that range, while generating the prime numbers that come in between 

-reply by Jimmy™

 

[iGuest 3]

Prime number generationPrime Number Generator

Last weekend I was thinking about something else completley when I came up with a prime number generator schema.

(Well I was thinking of prime numbers and their relationship with irrational numbers, it's a long story.)

I would take say a megabyte string of ascii 0s, throw in a 1 at position 2 and multiply that 2 by every number between 2 and 500000 flipping the ascii 0 to a 1 for all those positions.

The next 0 after the 2nd position will be a prime.

report that position 3 and do the same thing to it.

The next 0 after the 3rd position will be a prime 5.

As it goes into higher numbers it actually speeds up.  Fewer multiplications are required to reach the million mark.

Continue doing this for all numbers until 500000, 500001 cannot be multiplied by 2 and stay under a million.

Done.

And I am wondering just who's prime number generator have I duplicated? Because I am really not that smart.

Anyway I will sit down and design this using ascii byte and maybe not lose intrest before I convert it to nibbles.

(nibble because of much more storage space and possible speed up using the CPU registers.)

I will check back next week and post the program if it works.

-reply by Icecycle

[emiliano1405241587 0]

You are missing something, the divisors of a number start repeating after the squareroot of the number, so, the prime test would be more efficient if it breaks when it reaches the sqrt of the number. And also remember that there are several formulas that *MAY* return a prime number, you always have to test it.

I have made an algorythm that only takes 18 seconds to calculate the first 100000 prime numbers in my athlon xp 2500+
(I made it first for python and is my first progam in C++ so I apologize if it doesn`t have much style).

#include <iostream>#include <math.h>using namespace std;int main() {	start:	unsigned long m,x,d,mo,rc;	bool p;	string f;	cout << "how many primes do you want? ";	cin >> m;	cout << "\nfrom what number start? ";	cin >> x;	if (x <= 2 && m >= 1) {		cout << "2\n";		x = 2;		m--;	}	if (x <= 3 && m >= 1) {		cout << "3\n";		m--;	}	if (x%2 == 0) {		x++;			}	while (m >= 1) {		p = true;		d = 1;		rc = sqrt(x);		while (d <= rc && p) {			d++;			d++;			mo = x%d;			if (mo == 0) {				p = false;			}		}		if (p) {			cout << x << "\n";			m--;		}				x = x + 2;		if (m <= 0) {			break;		}			}	cout << "repeat? y/n ";	cin >> f;	if (f == "y") {		goto start;	}	else {		return 0;	}	}

[iGuest 3]

NEEDHELP!!Prime Number Generator

NEED HELP TO GENERATE PRIME NUMBERS ONLY USING THIS FORMAT...ANYONE ?

 

for(k=0;k<20;k++){		for(m=2;m<k+5;m++)	   {			   if((k+5)/m*m==k+5)   	    printf("%d,",k);    }}