02-13-2012, 11:51 PM
I have seen a couple ways that test numbers for primality.
I saw this solution on cplusplus.com
Lets say we have a prime number. This is 1033.
The above solution goes through a lot of tries to determine this number.
I also see a whole bunch of primality tests that only count as high as the square root of that prime number. I don't understand those at all (I'm stupid, keep this in mind).
So what I did was made this.
What this does is it checks and sees if the number is divisible evenly by two. No prime number other than 2 is divisible by 2. I forget to return true if the number is two, but just look past that for a little bit.
If the number isn't divisible by two, we set a counters iterator to 3 and then we iterate by twos to avoid checking it for even numbers. That cuts about half the work.
What I also do is I take the number I am testing and add one to make it even, then I divide that number by two to get half of the number.
Seeing as no number will ever be divisible by something greater than half of itself, I can assume it is safe to do so. This will also cut the work down by half.
To prove this, i'm going to work out the number 53 (which is prime) using a brute method.
If you take the number 53 and attempt to divide it by every number between 2 and 52, you end up checking it 50 times.
If you use the other method, you take that number, add one and divide it by two.
53 + 1 = 54.
54 / 2 = 27.
That's two operations so far.
Then we start at 3 and work all odd numbers from that to 27.
With the two operations we did adding and dividing, we come out with 15 operations. Only 13 of which actually check the number.
That is a 70% decrease in checks performed. This is just a smaller number however. Let's try a number like 1033 (which is prime).
Brute: 1030 checks
Other: 258 checks
74.59% decrease in checks from brute to other.
This makes me believe that the higher the number the more effective the other way compares to a brute method. (Which is probably common knowledge and I just made a dumb ass out of myself for saying so)
My math probably sucks and I am not doing the best I could be. So I want to see how you guys can do better. Hell, I could even be stupid for counting how many checks are preformed in the first place. I might have also fudged up a couple things with the percentages & other stats I threw at you, so if I did, I apologize in advanced.
But yeah, I just want to see how you guys do better cause I really need to find faster ways of doing things like this.
I saw this solution on cplusplus.com
Code:
bool prime;
int next;
for(next = value+1; ; next++){
prime = true;
for(int i = 2; i*i <= next; i++){
if (next % i == 0) prime = false;
}
if(prime) break;
}
cout << next;Lets say we have a prime number. This is 1033.
The above solution goes through a lot of tries to determine this number.
I also see a whole bunch of primality tests that only count as high as the square root of that prime number. I don't understand those at all (I'm stupid, keep this in mind).
So what I did was made this.
Code:
int is_prime(int tprime)
{
if(tprime % 2 == 0) return false;
for(int i = 3; i <= ((tprime-1)/2); i+=2)
{
if(tprime % i == 0) return false;
}
return true;
}What this does is it checks and sees if the number is divisible evenly by two. No prime number other than 2 is divisible by 2. I forget to return true if the number is two, but just look past that for a little bit.
If the number isn't divisible by two, we set a counters iterator to 3 and then we iterate by twos to avoid checking it for even numbers. That cuts about half the work.
What I also do is I take the number I am testing and add one to make it even, then I divide that number by two to get half of the number.
Seeing as no number will ever be divisible by something greater than half of itself, I can assume it is safe to do so. This will also cut the work down by half.
To prove this, i'm going to work out the number 53 (which is prime) using a brute method.
If you take the number 53 and attempt to divide it by every number between 2 and 52, you end up checking it 50 times.
If you use the other method, you take that number, add one and divide it by two.
53 + 1 = 54.
54 / 2 = 27.
That's two operations so far.
Then we start at 3 and work all odd numbers from that to 27.
With the two operations we did adding and dividing, we come out with 15 operations. Only 13 of which actually check the number.
That is a 70% decrease in checks performed. This is just a smaller number however. Let's try a number like 1033 (which is prime).
Brute: 1030 checks
Other: 258 checks
74.59% decrease in checks from brute to other.
This makes me believe that the higher the number the more effective the other way compares to a brute method. (Which is probably common knowledge and I just made a dumb ass out of myself for saying so)
My math probably sucks and I am not doing the best I could be. So I want to see how you guys can do better. Hell, I could even be stupid for counting how many checks are preformed in the first place. I might have also fudged up a couple things with the percentages & other stats I threw at you, so if I did, I apologize in advanced.
But yeah, I just want to see how you guys do better cause I really need to find faster ways of doing things like this.
