Finding Primes?

[Dillinger4]

Yes i know that this question has been ask many times before but after doing a seach in here and also on google i was unable to find a simple example. I know a prime number is a number that is evenly divisible by itself and one. Now what is the most simple way to find out if a number is prime? Thanks.

[ironhide]

A very simple algorithm

Dim factorFound As Boolean
    Dim cnt As Single
    
    cnt = 2
    num = 8
    While cnt <= Int(Sqr(num)) And Not factorFound
        If num Mod cnt = 0 Then
            factorFound = True
        End If
        cnt = cnt + 1
    Wend
    
    If factorFound Then
        MsgBox "not prime"
    Else
        MsgBox "prime"
    End If

[alkatran]

That's a very slow way to find primes, once you get higher up. You'll save time if you only test against previously found prime numbers instead of every number.

[Acidic]

If you don't care about missing some primes, try doing n!+1
I've never tried this but it should give primes, maybe not all the time and definately not all of them, but there you go.

[sql_lall]

One problem with storing all previous primes ( = using a sieve) is that this takes up memory. If u use RAM, you are very limited, and need to reload everything if you are wanting to increase your number of primes found.

An efficient way i found, which is resumable instantly, is to only check numbers = 30k + {1,7,11,13,17,19,23,29} against those numbers 30k + {...} up to its square root.

Of course, you can enhance slightly to 210k + {1,11,...} or even 2310k + {1,13,...} but theese don't improve the accuracy that much.

Oh, and if you are using a simple loop like the one in the origional post, only check odd numbers, start the factor to test at 3, and increment by two each time. This reduces you overall running time by a factor of 4!

i.e.

 
for(a=3; a < ... ; a+=2){
for(c=3; c*c<a; c+=2){
  if(a % c == 0)...
}}

[Dillinger4]

Ok we are getting off topic again. All i want to know is what is the basic mathematical way of finding primes.

[Acidic]

There is no formula to make primes or else they wouldn't be primes.
To make a list of primes you have to go through each number (or odd number to speed things up), divide it by all numbers smaller than itself and acheck the lengths of the answers. If any of the answers don't have decimals, then it is not a prime.

Obviously this can be sped up more, for example when checking the number 17. it doesn't divide by 2 or 3. there is no need to check 4 as that's only a mulitple of 2. then check 5, there is also no need to check 6 and it is a multiple of 2 and 3.
so as someone suggested, you only need to divide it by the already found primes.

[NoteMe]

There is algorithms for finding primes. One year after the other it has been developed a new algorith.


Last year it was an inian guy who found a new and better way. He talked about to the math teacher at Yale or something last year, and only 2-3 guys over there could more less get any sense from what he was talking about....

So if you want to find some primes. Then listen to Acidic...

[Acidic]

Originally posted by NoteMe
So if you want to find some primes. Then listen to Acidic...

I made a valid post

[NoteMe]

Originally posted by Acidic

I made a valid post

More or less...I was about to point out that you you where talking about even numbers...an even number can never be a prive...so that would just be redundant work anyway...

[Dillinger4]

Posted BY NoteMe
an even number can never be a prime

Ah yes i didn't even think of that. An even number is always evenly divisible by 1, 2, and itself so it cannot be prime.

[wossname]

Originally posted by NoteMe
only 2-3 guys ... could more less get any sense from what he was talking about....

A bit like Bodwad then.

[Dreamlax]

Originally posted by NoteMe
More or less...I was about to point out that you you where talking about even numbers...an even number can never be a prive...so that would just be redundant work anyway...

An even number can so be a prime! 2 is a prime number. A prime number can be defined as a number that has only two integer factors, the number itself, and one.

[NoteMe]

Originally posted by Dreamlax
An even number can so be a prime! 2 is a prime number. A prime number can be defined as a number that has only two integer factors, the number itself, and one.

Yeah, but everyone knows that two is a prime.

Lets say N is the number you are testing.

Start with N = 2

2 is a prime.

then add 1. Then test 3. 3 Is a prime.

then it is no need to test 4, so then you add 2 to N, and then you test that number, then you add 2 more to N, because there is no need in testing 4, 6, 8 and so on....sorry for not pointing tht out, but I though everyone understood it...

[beros87]

hi,
there is an old mathematical way to find primes.
for example if you want to find the primes between 1 and 100,
write down all the numbers between 1 and 100 then start with 2.
2 is a prime, continue by eliminating all the multiples of 2. do that to all the numbers.
at the end. the numbers that you didn't eliminate are the prime numbers.

[NoteMe]

Originally posted by beros87
....continue by eliminating all the multiples of 2....

What do you mean by that....take away all the numbers that you can multiply with 2 to get?

[beros87]

not only the numbers multiple of 2, but also the numbers multiple of 3...5 ( you have just eliminated 4 that is why you don't take it)
and you do it with all numbers.
note that 2,3, 5... are not eliminated, their multiples are eliminated, they are primes.
you continue and do that with all the numbers left, and those who aren't eliminated are the prime ones.

[NoteMe]

Now I get what you mean...yeah that works...but I think if I am not wrong, that is all ready said in this thread some where...

But yeah, that is the fastest known working way that is 100% sure. All other faster algorithms has a minor fault...

[Darkwraith]

That is how the Sieve of Erastothenes works.

[Something Else]

Originally posted by sql_lall
...An efficient way i found, which is resumable instantly, is to only check numbers = 30k + {1,7,11,13,17,19,23,29} ...

Implying , if we say L = 30, that L is the multiple of Primes up to a certain point, then everything in {} are the primes from the highest prime factor of L, + 1, to L itself. So, looking at:

Of course, you can enhance slightly to 210k + {1,11,...}

Then One must assume 121 is NOT inside {1,11,...}, being nonprime, so 210*1 + 121 is never checked.

Unfortunately, 210*1 + 121 = 331.

331 is prime.


Does 210k + {1,11,...} check 331???


-Lou

[ZaidGS]

there are two tips i can give about effiently finding a prime number.
- check only for odd numbers, cuz except the 2, all prime numbers are odd.
- check only those less than or equal to square root of number you are searching for
something like:

Check(2)
For i = 3 to Sqr(N) step 2  'N is the number we are making sure is prime or not
Check(i)
Next i

you might find this part of code from a program i made back in my qbasic days usefull.
it factorizes a given number like:
INPUT: 9075
OUTPUT: 3 * 5 ^ 2 * 11 ^ 2

700     Print "Results for:"; tn
701     Print
710     q = tn
716     i = 2
717     E = 0
718     S = q
720     If q / i = Int(q / i) Then
721         E = E + 1
725         q = q / i
726     End If
730     If i > q / i And q = i Then
731         E = E + 1
732         GoTo 770
733     End If
735     If i > q / i And q <> i Then GoTo 775
740     If S > q Then GoTo 718
745     If E > 1 Then Print ; i; "^"; E; "*";
746     If E = 1 Then Print ; i; "*";
750     If i = 2 Then i = 3 Else i = i + 2
760     E = 0
765     GoTo 718
770     Print i; "^"; E
771 End
775     If E = 0 Then Print q
776 If E = 0 Then End
780     If E = 1 Then Print i; "*"; q
781 If E = 1 Then End
785     Print i; "^"; E; "*"; q

if the code seems childish, u might want to know that i made it maybe when i was 10 years old

[wossname]

2 years ago I sat down and invented a prime number finding algorithm.

It was all my own work, I had barely researched what primes were beyond "Divisible only by itself and 1". About a week later I had perfected the algorithm and optimised it to run as fast as it would go.

I benchmarked it and was pleased with it.

Then I find out that it is more or less exactly identical to about 15 other guy's algorithms from the last 50 years. Damn.

Well at least I'm as cleveras at least 1 bloke from Yale, another 2 from MIT and a woman at CalTec. So its not all bad.

I must be a jeyneus.