 |
 | The Best And Easy Of Prime Number Is
mehranrezaie | 1:44 28 Oct '08 |
|
|
#include <iostream>
using std::cout;
using std::cin;
void main()
{
inti,num,sum;
cout<<"Enter Your Number\n";
cin>>num;
for(i=2;i<num;i++)
{
sum=num%i;
if(sum==0){
cout<<"your Number Isn't Prime\n";
break;}}
if(sum!=0)
Cout<<"Your Number Is Prime\n";
}
|
|
|
|
|
| LOL
baks256 | 5:09 31 May '07 |
|
|
 is it a high speed algorithm?
you must be kidding
I advise you to use algorithms base on pseudoprime numbers. it is much more faster, besides, the probability of mistakes is very small.
|
|
|
|
|
| Re: LOL
Mariano Abdala | 5:22 31 May '07 |
|
|
I advise you to read previous topics, what you're talking about has being already replyed.
Mariano, el estupefacto. 
|
|
|
|
|
| high speed prime numbers
prasofty | 21:43 20 May '07 |
|
|
in this program i got prime no's below the give no:
can u give me an idea ..........
first 100 prime no;
not below thwe 100 prime no?
|
|
|
|
|
| Re: high speed prime numbers
Mariano Abdala | 2:03 21 May '07 |
|
|
Hi! Sure, I guess you could just uncomment this line
But I would suggest you to write them donw on a File, instead of printing them on screen.
Greetings!
Mariano, el estupefacto.
|
|
|
|
|
| High Speed ?
amircorrtec | 19:19 18 Feb '07 |
|
|
Hi
I thnink it is more efficient than others but the problem is it is not able to find the biggest one.
Don't try for infinity.
Amir Ali
|
|
|
|
|
|
|
|
 | I have a algorith plus quick that.
MauricioFox | 21:44 22 Jul '06 |
|
|
and is the next:
All Prime Numbers are write whit the next formulate:
6n+1 or 6n-1 this is very easy to demostrate. but the problem is that all number generate with 6n+1 or 6n-1 are prime, later you need know if this is a prime number or no... well the solution is the next
example: we supose that M=6n+1 and we need know if this number M is or not prime.
for i=0 to i=M^(1/2)
if(M%i==0)then
return "this is no a prime"
return "this is a prime"
MauricioFox
vi japi
|
|
|
|
|
| Hmmmm......
Paul Conrad | 21:28 11 Jul '06 |
|
|
There are faster algorithms for finding primes.
|
|
|
|
|
| Yet one more suggestion.
petrowi | 12:21 20 Jun '06 |
|
|
A while back (10 years) I had an implementation in Turbo Pascal 7 (does anyone remember it? ) ) and it calculated the first 1bln primes in about a week on AMD K2 266Mhz/32Mb RAM machine.
Two things are applicable here: restructuring the bitmap and "sliding window".
What happens is you're keeping all the calculated values in order to reuse them. To reach 4bln you'd need 256Mb of memory... hmm 256Mb x 8bits = 2Gbits, but it's obvious that every even number is divisible by 2, so there is no need to store a bit for it. You can go further - in every 6 numbers 4 are not prime - 3 are divisible by 2, 2 are divisible by 3 and 1 is divisible by both 2 and 3. Going further doesn't make much sense - it gets too complicated and starts slowing down because of index calculations.
This way you wouldn't even need to "init" your array for the number 2.
Another thing you can do if you don't need all the calculated primes in memory, but just to output them:
If you output the maximum number you use to index the bitmap to check if your number is divisible by some prime you'll see it won't go too far. For 4bln it's around 63000 - the square of your largest found prime. You can split your bitmap into two bitmaps - one that holds the primes 2,3..sqrt(MAX_PRIME_EVER_TO_FIND) and another one that you calculate and output in a cicle (your "sliding window"), then repeat the cicle by assuming a different number to correspond to your sliding window's first element.
Sten
|
|
|
|
|
| Yet another suggestion
montclaris | 18:29 24 Jan '06 |
|
|
You could change the loop boundaries to improve complexity of your algorithm.
The inner loop could be set to begin at bound j = i*i instead of j = i*2. This is valid because at this point of the loop, any number below i has already discarded all its multiples. So given any number a below i, a*i is a multiple of a and was therefore discarded previously (loop invariant). There's no point discarding it once more.
Then, the upper bound of your outer loop could be improved by stopping the loop when condition i*i > topNumber is met. When i*i is above topNumber, the inner loop would generate its smallest multiple (j = i * i) > topNumber. After this point you would never enter your inner loop because of its upper bound, so better stop sooner than later.
|
|
|
|
|
| Wheel Factorization
danielibarnes | 13:06 11 Nov '05 |
|
|
|
| False Primes
jmoral4 | 11:30 24 Aug '05 |
|
|
Perhaps I missed the point of this exercise but... the 'speedier' algorithm above returns false primes. It treats numbers like 9 and 15 as prime numbers. Perhaps I took the implementation too literally.
The first algorithm listed above seems to work correctly. I evaluated Int.MaxValue.
I happened to be researching Encryption algorithms and I decided to write a short Prime Number Generator after looking at how RSA encryption works.
|
|
|
|
|
|
|
Hello jmoral4!
I tried the first 50 numbers by copying the code on the page and the result was:
1
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
16 out of 50 prime numbers found.
As you can see 9 and 15 aren't on the results. But it might be a bug somewhere. Would you please like to tell me exactly what you've done to get that numbers??
Thanks for the comments!
Mariano, el estupefacto.
|
|
|
|
|
|
|
You're absolutely right, thanks. I must have made a mistake transcribing as I can't copy and paste between our internal and external networks. Makes a lot more sense now 
|
|
|
|
|
|
|
No problem! Could happend to anyone.
If you need some help on this or if you would like to use it on your work, let me know and I'll do my best to help you.
Mariano, el estupefacto.
|
|
|
|
|
|
|
I think that the second loop should also start with 2. Remember that all bits are initially set to true, but the ones that are set to false start from 4, so it appears that the first are all primes? Don't think so.. So either you set number[0] and number[1] to false, or you start the second loop from 2 instead of 1
|
|
|
|
|
| I've done something similar
Yan Yorga | 3:47 15 Dec '04 |
|
|
I have no idea why I started doing it but I did.
My first step was the same as yours except I increment by 2 and I store the result of the division and if it is less than the next prime to divide by, the number being tested must be prime.
I then looked at eliminating numbers from a number line by 'stepping' in prime numbers. I realised that with this method if you are not starting from 0 you need to store the largest multiple of each prime that you have got to so you can resume later on OR you would have to divide n by each prime, round down the result and then multiply by the same prime. This gives you your new start point to begin stepping from.
I also considered changing the base and doing a 'step left' to eliminate sets of numbers but I don't know how to code that which is how I arrived here
Your arguement against using the faster probability method is that it is not definite. The only question you need to answer is can it eliminate numbers which are not primes faster than other methods. Then you can test the remaining possibilities with a definite algoritm. To perfect it you would need to find out where it becomes more efficient to stop eliminating numbers by doing more iterations and find out for certain.
I think the advantage of the first method is that it can be picked up at any point by just recording the last prime number that was used to divide by. It's only problem is you need to know all the prime numbers up to the square root of the number you are testing.
|
|
|
|
|
|
|
Hi! Tnx for the comment. About the probability method, my intention never was to discredit it. I think it's great, but it can't be aplied to 'my' method.
I've been investigating a little more about what my application was capable of, and discover that most of those 10 minutes I talk about, the machine was swapping memory onto the HD. And about 10 SECONDS were really used to run the program algorithm. I did this program in C# as a way to probe that The Sieve Of Erastotenes was the best way of calculating ALL prime numbers in a computer. I think I've probe it right. To extend this program, it would have to be written maybe in assembler and run as much as possible into RAM and the rest of it into a HD o any large storage unit.
In fact, most of the time of the whole process is getting a place to storage the result and a little bit of it to run the algorithm. That's way, I think, most of developmet to extend the program would be destinated to program an efficient way to get space and storage the results.
Way did you get interested into calculating prime numbers? Are you working on something related to it?
Greetings.
Mariano, el estupefacto.
|
|
|
|
|
| One More Suggetion
Prashant Mishra | 15:57 21 Oct '04 |
|
|
You can use binary search and increase the spead of alorithm.
|
|
|
|
|
| High speed? I think not.
Jörgen Sigvardsson | 9:29 20 Aug '04 |
|
|
Your algorithm is quadratic [edit]n*log(n)-ish[/edit] in time complexity, and linear in space complexity. It's neither fast nor efficient for anything but very small prime numbers.
As pointed out earlier, have a look at the Rabin-Miller Prime Number Test[^]. It has logarithmic time complexity, and constant space complexity.
To find a prime number is easy using the test. Pick a number of the magnitude you'd like the prime number to have. Test the number using 20 something iterations. If the test says "No", subtract or add 1 to your number and do the test again. Repeat until prime number "probably" found.
--
Denn du bist, was du isst!
Und ihr wisst, was es ist!
Es ist mein Teil...?
|
|
|
|
|
|
|
So, that big algorithm, just give you 'probable prime numbers'? That efficiency!
In fact, you could see these my way. If something is probable but not sure, you can have for sure that's gona fail. That's the point of a realy great LAW, the murphy's law. So thanks, but's no use on Rubin-Miller's for me.
Mariano, el estupefacto.
|
|
|
|
|
|
|
Ask yourself: what's the point in calculating a bunch of prime numbers unless your trying to find the biggest one? If you are, then you'd have to switch over to Mersenne based[^] algorithms.
For practical uses, prime numbers are only useful for hash tables (for optimum distribution of keys) and cryptography. I can't think of any other application on top of my head. Anyway, in those cases, you just want to pick a prime number. In the hash table scenario the criteria is "a prime number at least as large as the number N", and in the cryptography scenario, the criteria is "a random prime number".
In both scenarios, the associated algorithms won't break if it's not a prime number. In the hash table scenario, the distribution of keys will be slightly less efficient. In the cryptography scenario, the only requirement is that the probability should be high enough to make it unfeasible for the cryptanalysist to use the probability to his/her advantage.
The Rabin-Miller algorithm is smart in the way that it can be set in feedback mode. You can retest over and over again. For each test, the probability that the number is a composite number is 1/4 or less. So, if you do 20 iterations, the composite number probability would be 9.094947017729282379150390625 * 10-11%. If you are still worried, do 20 more iterations and you have a probability of 8.2718061255302767487140869206996 * 10-23%. Pretty good odds if you ask me.
--
Denn du bist, was du isst!
Und ihr wisst, was es ist!
Es ist mein Teil...?
|
|
|
|
|
|
|
Jörgen Sigvardsson wrote:
what's the point in calculating a bunch of prime numbers unless your trying to find the biggest one?
Actually it isn't about finding the biggest one, but all of them. That's what I try to do. That's what this code does.
Probability [different than 1] implies a quote of failure. Even most if the number of tries tends to infinite. 
Mariano, el estupefacto.
|
|
|
|
|
|
|
|/| / |Z ! / || [] wrote:
Probability [different than 1] implies a quote of failure. Even most if the number of tries tends to infinite.
You know.. a fight against infinity is a hard battle.
--
Der Metzgermeister
|
|
|
|
|
