Thread: Prime number algorithm

Hello.

Could anyone help me with a prime number algorithm?
I'm not asking for direct code, but pesudo would be nice...
This is what I currently got

Code:

int isPrime(const int number){

	int i; // variable for the loop

	double d; // variable to store the division and hold the decimals
	int x;	// variable to help check if a division had decimals

	if( number <= 1) return 0; // if 'number' is equal to 1, it's not a prime number "The number 1 is by definition not a prime number" - Wikipedia

	for(i = 2; i != number; ++i){ // 'i' must start at 2

		d = number/i;
		x = d;	// and integer cannot hold decimals

		if(d == x) return 0;	// if d and x are equal, then it can't be a prime
	}

	return 1;
}

Thanks in advance!

Here's a handy speed up for your algorithm:

A number is prime if it can not be evenly divided by any number UP TO (including), the square root of that number.

Code:

int isPrime(const int number){

	int i; // variable for the loop

	double d; // variable to store the division and hold the decimals
	int x;	// variable to help check if a division had decimals

	if( number <= 1) return 0; // if 'number' is equal to 1, it's not a prime number "The number 1 is by definition not a prime number" - Wikipedia

	for(i = 2; i != number; ++i){ // 'i' must start at 2

		d = number/i;
		x = d;	// and integer cannot hold decimals

		if(d == x) return 0;	// if d and x are equal, then it can't be a prime
	}

	return 1;
}

Instead of working with a double (which is sure to slow things down), what about using integers, with the modulo operator: %?

if(number modulo testNumber equals zero) kind of stuff.

hmm... that's actually brilliant
Thanks!

Just to share my snippets I'm working on! (and done with now xP)

Code:

// Problem 5 - Write a function that checks if the passed number is a prime number

int isPrime(const int number){

	int i; // variable for the loop

	if( number <= 1) return 0; // if 'number' is equal to 1, it's not a prime number "The number 1 is by definition not a prime number" - Wikipedia

	for(i = 2; i != number; ++i){ // 'i' must start at 2

		if(number % i == 0) return 0;	// if there arem't any 'left overs' after the divide, then it can't be a prime
	}

	return 1;
}


// Problem 6 - Write a function that checks if the passed number is a 'perfect' number

int isPerfect(const int number){

	int sum = 0;	// variable that will hold all the dividors and then we check if it adds up to 'number'
	int i;			// variable for the loop

	for(i = 2; i <= number; ++i){

		sum += number/i;

		if(number/i == 1) break;
	}

	if(sum == number) return 1;
	else return 0;

}

I don't get it... What would the square root be doing/helping with?

You can read the entries for the Prime Number Generator contest for more ideas.
EDIT:

Originally Posted by Adak

It's a rule in mathematics. If any number has no number that evenly multiplies into it, which is less than or equal to, it's square root, then it's a prime number.

Say you wanted to test the number 257. Math tells us that if 257 can't be divided by any number less or equal to it's square root, then it's a prime number:

Maybe it would be easier to understand if we approach it from the point of view of the prime factors of a composite rather than stating it as a rule for primes.

Consider an arbitrary integer n > 1 such that n is a composite number. It follows that n has a prime factor p, and another factor q such that p * q = n. If p is equal to q, then p is the positive square root of n, by definition of square root. Consequently, if p is less than q, then p is less than the square root of n. But if p is greater than q, then consider that q must either be prime or a product of primes. If q is not prime, then it must be a product of primes, each of which is less than the square root of n. Hence n must have a prime factor less than or equal to its square root. Thus, we only need to test with primes less than or equal to the square root of the candidate integer for primality testing by trial division.

2 the number is even
924 is divisible by 2 since
924 is even.

3
The sum of the digits is divisible by three
924 is divisible by 3 since the sum
of the digits 9 + 2 + 4 = 15 and 15
is divisible by 3

4
the numbers formed by the last two digits of the
number is didisible by 4
924 is divisible by 4 cause 24 is divisible by 4
5
the number ends in 0 or 5
265 is divisible by 5 since the number ends with 0 or 5
6
the number is divisible by both 2 and 3
924 is divisible by 6 since since it is since it tested true
by both 2 and 3
8
the number formed by the last digits of the number
is divisible by 8
5824 is divisible by 8 since the last three digits
824 is divisible by 8
9
the sum of the digits of the number
is divisible by 9
837 is divisible by 9 since the sum of the digits
8 + 3 + 7= 18 and is divisible by nine.

If any of these test true then the number is not prime.



Personaly I'd use a count to keep tract of the numbers divisible If the count went above 1 then reset count and start at the next number. if it finds a prime number print it out
You only have to check with prime numbers and you only have to check up to the sqt() of the number you want to know is prime. Also Eventhought its cheating I would count by two on the numbers to be tested.