Programming Forums > Application Development > C++

Ooble · May 17th, 2005, 10:31 AM

Quote:

Originally Posted by Nuticulus

Thirdly, (and this one's common sense), you only need to test half the numbers up to the value of the tested number. I.e, you know that x will not be cleanly divisible by a number that's greater than x/2, apart from x.

Actually, because you're multiplying two numbers, you only need to go up to the square root of the number. Make sure you test the square root though, otherwise 4, for example, will be found to be a prime.

Here's a program I wrote a while back when I was bored:

(Toggle Plain Text)

#include <stdio.h>
#include <math.h>

#define true 1
#define false 0

int is_prime (double num)
{
	long i;
	
	if (num < 2)
	{
		return false;
	}
	else if (num == 2)
	{
		return true;
	}
	else
	{
		for (i = 3; i <= sqrt(num); i += 2)
		{
			if ((num / i) == ceil(num / i))
			{
				return false;
			}
		}
		
		return true;
	}
}

int main ()
{
	double i;
	
	for (i = 1; i > 0; i++)
	{
		if (is_prime(i))
		{
			printf("%.0f\n", i);
		}
	}
	
	getchar();
	return 0;
}

thomzor · May 17th, 2005, 11:19 AM

unsigned long prime_array[prime_count];

change that line ^ into the one below (in my program)

unsigned long * prime_array = new unsigned long [prime_count];

with the 1st line u cant even calculate 2mil, now u can go as far as 4294967295(if im correct) 4 bytes that is

i estimate 10 mil will take about 30 minutes (quite alot eh, on a p4 2,4ghz that is) :p

@Ooble
thanks for the tip regarding the sqrt,
the speed will increase at higher numbers perhaps, but a sqrt is quite a few clock ticks so not all that usefull at lower #'s (i think, not sure)

i'll try it out anyway :p

Ooble · May 17th, 2005, 2:16 PM

When you hit ten million or so, you'll start to notice the difference.

thomzor · May 17th, 2005, 2:34 PM

Quote:

Originally Posted by Ooble

When you hit ten million or so, you'll start to notice the difference.

true

i made a program for just 1 number, tried your trick and it's really a great improvement

mackenga · May 19th, 2005, 3:39 PM

The Sieve of Eratosthenes is a much better algorithm for finding prime numbers in a given range. See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for a nice description. (If wikipedia takes a while to respond, have patience; it's sometimes slow, but it's always excellent).

brkstf · May 19th, 2005, 4:22 PM

i could be wrong, but doesn't the "sieve" method require an array of integers the size of the range. for instance, if we wanted to find all primes between 2 and 20, we make an array with 19 members, and we only get eight primes (2, 3, 5, 7, 11, 13, 17, 19) for our memory used. as primes get fewer and farther between, this ratio gets much much worse. the calculation is extremely fast, but the memory overhead is ridiculous.

if you're really into prime numbers, check out the reimann zeta function, which, for no reason any non-mathematician can understand, can predict the nth prime as far as anyone has calculated.

Ooble · May 19th, 2005, 4:30 PM

Has anyone ever read Music of the Primes by Marcus du Sautoy? I've been to two lectures by the man, and he's really onto something.

thomzor · May 19th, 2005, 4:31 PM

ye i gave up on it :p

i was all happy and stuff that i could do 2->1.000.000 in 3 minutes

then i found a site of a guy that did it in 2.13 seconds, i was pissed off =D? -.-

basically he had single bits in memory and used Erastothenes and several other optimizations

i don't think i can reproduce what he did becase it was quite complicated

anyways, feel free to continue on with the discussion

Ooble · May 19th, 2005, 4:34 PM

My way takes 23 seconds on my PC. Guess it's time to get optimising.

thomzor · May 19th, 2005, 4:37 PM

Quote:

Originally Posted by Ooble

My way takes 23 seconds on my PC. Guess it's time to get optimising.

^^

from what i remember, the dude had single bits in memory and used macro's to manipulate the bits

he started the way i did ^^, then he improved the program step by step explaining it,

the final stage was a program which could go on unlimited swapping disk & memory, was quite interesting to read

May 17th, 2005, 2:16 PM	#13
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	When you hit ten million or so, you'll start to notice the difference. __________________ Me :: You :: Them

May 19th, 2005, 3:39 PM	#15
mackenga Professional Programmer Join Date: Mar 2005 Location: Glasgow, Scotland Posts: 317 Rep Power: 4	The Sieve of Eratosthenes The Sieve of Eratosthenes is a much better algorithm for finding prime numbers in a given range. See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for a nice description. (If wikipedia takes a while to respond, have patience; it's sometimes slow, but it's always excellent).

May 19th, 2005, 4:30 PM	#17
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	Has anyone ever read Music of the Primes by Marcus du Sautoy? I've been to two lectures by the man, and he's really onto something. __________________ Me :: You :: Them

May 19th, 2005, 4:34 PM	#19
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	My way takes 23 seconds on my PC. Guess it's time to get optimising. __________________ Me :: You :: Them

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

May 17th, 2005, 11:19 AM	#12
thomzor Newbie Join Date: Apr 2005 Location: The Netherlands Posts: 20 Rep Power: 0	unsigned long prime_array[prime_count]; change that line ^ into the one below (in my program) unsigned long * prime_array = new unsigned long [prime_count]; with the 1st line u cant even calculate 2mil, now u can go as far as 4294967295(if im correct) 4 bytes that is i estimate 10 mil will take about 30 minutes (quite alot eh, on a p4 2,4ghz that is) :p @Ooble thanks for the tip regarding the sqrt, the speed will increase at higher numbers perhaps, but a sqrt is quite a few clock ticks so not all that usefull at lower #'s (i think, not sure) i'll try it out anyway :p

May 19th, 2005, 4:22 PM	#16
brkstf Programmer Join Date: Feb 2005 Posts: 89 Rep Power: 4	i could be wrong, but doesn't the "sieve" method require an array of integers the size of the range. for instance, if we wanted to find all primes between 2 and 20, we make an array with 19 members, and we only get eight primes (2, 3, 5, 7, 11, 13, 17, 19) for our memory used. as primes get fewer and farther between, this ratio gets much much worse. the calculation is extremely fast, but the memory overhead is ridiculous. if you're really into prime numbers, check out the reimann zeta function, which, for no reason any non-mathematician can understand, can predict the nth prime as far as anyone has calculated.

May 19th, 2005, 4:31 PM	#18
thomzor Newbie Join Date: Apr 2005 Location: The Netherlands Posts: 20 Rep Power: 0	ye i gave up on it :p i was all happy and stuff that i could do 2->1.000.000 in 3 minutes then i found a site of a guy that did it in 2.13 seconds, i was pissed off =D? -.- basically he had single bits in memory and used Erastothenes and several other optimizations i don't think i can reproduce what he did becase it was quite complicated anyways, feel free to continue on with the discussion

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Prime numbers