Omnimaga

General Discussion => Other Discussions => Math and Science => Topic started by: Yeong on January 07, 2011, 04:25:15 pm

Title: Formula for getting prime number?
Post by: Yeong on January 07, 2011, 04:25:15 pm

Does it exist, if it does, can you tell me?(I need it to do mah APCS Homework D: )

Title: Re: Formula for getting prime number?
Post by: nemo on January 07, 2011, 04:27:35 pm

a prime number is defined as number whose only factors are 1 and itself. is that enough to start you off?

Title: Re: Formula for getting prime number?
Post by: Yeong on January 07, 2011, 04:28:57 pm

I know that :P
But I need to write a formula so Java can know if the number is prime or not
EDIT: never mind. I got it

Code: [Select]

boolean isPrime=true;
for(int k = 2 ; k < number ; k++)
{
if ( number/k == 0)
isPrime=false;
}

Title: Re: Formula for getting prime number?
Post by: nemo on January 07, 2011, 04:30:50 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:28:57 pm

I know that :P
But I need to write a formula so Java can know if the number is prime or not

ok... well knowing that the only factors of a prime number are itself and 1, theoretically, couldn't you test the range 2 through n-1 and see if the any of them are factors? of course this wouldn't work for two, but then just put if(n == 2) isPrime = true;

Title: Re: Formula for getting prime number?
Post by: AngelFish on January 07, 2011, 04:31:43 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:25:15 pm

Does it exist, if it does, can you tell me?(I need it to do mah APCS Homework D: )

With the exception of the definition of prime numbers, no known algorithm exists for finding prime numbers. The question is related to the Riemann Hypothesis, one of the longest standing unsolved mathematical problems in the world. If a formula was found (or proved not to exist), the Riemann Hypothesis could be either proven or disproven.

EDIT: Nemo, that works, but it's also computationally inefficient for larger numbers  :P

Title: Re: Formula for getting prime number?
Post by: nemo on January 07, 2011, 04:32:22 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:28:57 pm

I know that :P
But I need to write a formula so Java can know if the number is prime or not
EDIT: never mind. I got it

Code: [Select]

boolean isPrime=true;
for(int k = 2 ; k < number ; k++)
{
if ( number/k == 0)
isPrime=false;
}

try number = 2.
edit: nevermind

Title: Re: Formula for getting prime number?
Post by: Yeong on January 07, 2011, 04:33:41 pm

oops O_o

Code: [Select]

boolean isPrime=true;
for(int k = 2 ; k < number ; k++)
{
if (number==2 || number/k == 0)
isPrime=false;
}
EDIT: Aww Back to original

Title: Re: Formula for getting prime number?
Post by: nemo on January 07, 2011, 04:35:07 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:33:41 pm

oops O_o

Code: [Select]

boolean isPrime=true;
for(int k = 2 ; k < number ; k++)
{
if (number==2 || number/k == 0)
isPrime=false;
}
EDIT: Aww

no,

Code: [Select]

boolean isPrime=true;
for(int k = 2 ; k < number ; k++)
     if ( number/k == 0)
          isPrime=false;

works. 2 is not less than 2, so the loop skips and isPrime remains true anyway.

Title: Re: Formula for getting prime number?
Post by: Michael_Lee on January 09, 2011, 12:35:10 am

To minimize the computational time, you could just skip testing all the even numbers, and test only up to the square root of the number-to-be-tested.

Title: Re: Formula for getting prime number?
Post by: Hot_Dog on January 09, 2011, 12:39:01 am

It has been proven, by the way, that there is no largest prime number 8)

Title: Re: Formula for getting prime number?
Post by: z80man on January 09, 2011, 12:55:50 am

I once wrote a TI Basic program to find prime numbers that used this pattern I found among the spacing between primes. I think it was able to count out about 1000 primes in rhe first hour and could also save its state at any time so you wouldn't have to start over.

Title: Re: Formula for getting prime number?
Post by: jnesselr on January 09, 2011, 03:46:50 pm

Quote from: Hot_Dog on January 09, 2011, 12:39:01 am

It has been proven, by the way, that there is no largest prime number 8)

It's been proven in more than one way, too.

Quote from: z80man on January 09, 2011, 12:55:50 am

I once wrote a TI Basic program to find prime numbers that used this pattern I found among the spacing between primes. I think it was able to count out about 1000 primes in rhe first hour and could also save its state at any time so you wouldn't have to start over.

Very nice. I don't remember where it starts, but there is a point where primes are basically spaced 2, then 4 apart.  So, for example, starting with 1.  1+4=5. 5+2=7. 7+4=11. 11+2=13. 13+4=17, etc.

Title: Re: Formula for getting prime number?
Post by: Builderboy on January 09, 2011, 04:39:48 pm

I remember I once wrote a program in TiBasic which could find all the prime numbers from 1-999 in about 18 Seconds >:D The thing about the program is that you have to give it an upper bound and it will find all the primes up till that number.  And after you do that it can't go any farther, you would have to start over

Title: Re: Formula for getting prime number?
Post by: willrandship on January 09, 2011, 06:39:25 pm

I have a nice theory working too.

It'll take a bit of space, so....

Spoiler For stuff you care about:

Code: [Select]

Arrange your numbers in a matrix. The width determines the numbers you can eliminate.
Here's the basic concept. The width is a multiple of several prime numbers. If you multiply 3,5,and 7
together you get 105. In the 105 columns, you can eliminate every 3rd starting at 3, every 5th starting
 at 5, and every 7th starting at 7. You don't need to put in two, since you can simply eliminate every
other going down each column (-210 instead of -105)

Example using 3*5 (15)

0   1  2  3  4  5 6  7   8  9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

    1   2     4          7  8          11     13 14
    16 17     19         22 23         26     28 29
    31 32     34         37 38         41     43 44
    46 47     49         52 53         56     58 59

The more primes you multiply in (nonprimes are useless, eliminate no more rows) the more you can eliminate! yay!
Now for checkerboarding for multiples of 2:

    1                        7             11     13 
        17     19             23                     29
    31                     37             41     43
        47     49             53                     59

True, you eliminate two, but who cares? You don't lose any primes.

By the way, doing this exactly this way with 105 (0-104) give you 31.428% remaining, whereas 3 gives 33.333% It's exponentially less effective, but still waaay better than just -2.



Edited for better readability

Edit: Also, I find it worth noting that since the math involved in this is fairly simple, and not based on the size of the number, it is practical for use on RSA cracking :P

Title: Re: Formula for getting prime number?
Post by: jnesselr on January 09, 2011, 06:49:09 pm

Quote from: willrandship on January 09, 2011, 06:39:25 pm

I have a nice theory working too.

It'll take a bit of space, so....

Spoiler For stuff you care about:

Code: [Select]

Arrange your numbers in a matrix. The width determines the numbers you can eliminate.
Here's the basic concept. The width is a multiple of several prime numbers. If you multiply 3,5,and 7
together you get 105. In the 105 columns, you can eliminate every 3rd starting at 3, every 5th starting
 at 5, and every 7th starting at 7. You don't need to put in two, since you can simply eliminate every
other going down each column (-210 instead of -105)

Example using 3*5 (15)

0   1  2  3  4  5 6  7   8  9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

    1   2     4          7  8          11     13 14
    16 17     19         22 23         26     28 29
    31 32     34         37 38         41     43 44
    46 47     49         52 53         56     58 59

The more primes you multiply in (nonprimes are useless, eliminate no more rows) the more you can eliminate! yay!
Now for checkerboarding for multiples of 2:

    1                        7             11     13 
        17     19             23                     29
    31                     37             41     43
        47     49             53                     59

True, you eliminate two, but who cares? You don't lose any primes.

By the way, doing this exactly this way with 105 (0-104) give you 31.428% remaining, whereas 3 gives 33.333% It's exponentially less effective, but still waaay better than just -2.



Edited for better readability

Edit: Also, I find it worth noting that since the math involved in this is fairly simple, and not based on the size of the number, it is practical for use on RSA cracking :P

It actually does matter, because even if you had all the primes from 0 to n-1, it would still be just as difficult to search through them all.  So, no, it doesn't help at all with RSA.

Title: Re: Formula for getting prime number?
Post by: nemo on January 09, 2011, 06:50:49 pm

for those chrome users who cannot read willrandship's post.

Code: [Select]

Arrange your numbers in a matrix. The width determines the numbers you can eliminate.
Here's the basic concept. The width is a multiple of several prime numbers. If you multiply 3,5,and 7
together you get 105. In the 105 columns, you can eliminate every 3rd starting at 3, every 5th starting
 at 5, and every 7th starting at 7. You don't need to put in two, since you can simply eliminate every
other going down each column (-210 instead of -105)

Example using 3*5 (15)

0   1  2  3  4  5 6  7   8  9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

    1   2     4          7  8          11     13 14
    16 17     19         22 23         26     28 29
    31 32     34         37 38         41     43 44
    46 47     49         52 53         56     58 59

The more primes you multiply in (nonprimes are useless, eliminate no more rows) the more you can eliminate! yay!
Now for checkerboarding for multiples of 2:

    1                        7             11     13 
        17     19             23                     29
    31                     37             41     43
        47     49             53                     59

True, you eliminate two, but who cares? You don't lose any primes.

By the way, doing this exactly this way with 105 (0-104) give you 31.428% remaining, whereas 3 gives 33.333% It's exponentially less effective, but still waaay better than just -2.


Title: Re: Formula for getting prime number?
Post by: willrandship on January 09, 2011, 06:52:38 pm

I put it in a spoiler so It wouldn't take up the whole page, in the code for the monospace for laying out the matrices.

Title: Re: Formula for getting prime number?
Post by: nemo on January 09, 2011, 06:59:22 pm

Quote from: willrandship on January 09, 2011, 06:52:38 pm

I put it in a spoiler so It wouldn't take up the whole page, in the code for the monospace for laying out the matrices.

code automatically has a scrollbar for that reason. if you put code inside a spoiler, for chrome users, it's virtually unreadable. here is a screenshot.

Title: Re: Formula for getting prime number?
Post by: willrandship on January 09, 2011, 07:04:05 pm

/me shudders

Well, I've used chrome with no real complaints, firefox just has too many plugins to pass up :P

Title: Re: Formula for getting prime number?
Post by: AngelFish on January 09, 2011, 07:51:00 pm

What I don't understand is why anyone would need to use a sieve methods to find primes for a math class. If the assignment is to generate a list of primes, then there are plenty of lists already available online. If the assignment simply requires prime numbers, then a much more efficient primality test would be applicable

Title: Re: Formula for getting prime number?
Post by: willrandship on January 09, 2011, 08:00:00 pm

Oh, @Graphmastur,

I'm not saying you do it for all prime numbers, just a few. Then, you can simply take the remaining rows and add by the matrix width (x2 if you use an odd number)

It's only a gain of roughly 2% over simply adding by 4,2,then 4, then 2, then 4 through two columns arranged by 3 on Trial factoring, though :P

as in
1,2,3
4,5,6
7,8,9

Title: Re: Formula for getting prime number?
Post by: Galandros on January 30, 2011, 05:44:59 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:25:15 pm

Does it exist, if it does, can you tell me?(I need it to do mah APCS Homework D: )

No, there isn't any (known) formula to get the sequence of primes. But I don't know if it was proven mathematically that there is not such formula.
The difficulty to crack RSA depends on being hard to find primes and the interest on primes comes also from this.

There are formulas that give asymptotically the average of number of primes in an interval or probability of a random number being prime. See more in:
http://en.wikipedia.org/wiki/Prime_number_theorem

Title: Re: Formula for getting prime number?
Post by: jnesselr on January 30, 2011, 06:07:52 pm

There is nothing that says it can or cannot be true.  It would kinda fit into the category of P=NP, though. e.g., you can prove S times T equals a number, but finding S and T from that number would be a lot harder.

Title: Re: Formula for getting prime number?
Post by: Galandros on January 30, 2011, 06:16:25 pm

Quote from: graphmastur on January 30, 2011, 06:07:52 pm

There is nothing that says it can or cannot be true.  It would kinda fit into the category of P=NP, though. e.g., you can prove S times T equals a number, but finding S and T from that number would be a lot harder.

Yep, I think from what I read it falls on that category.
But almost everyone that works on the area admits that there is not such formula or even it can not exist.

There is the possibility some undiscovered area of Mathematics bring some solution to the problem of getting the primes sequence without going by number testing. Better keep an open spirit about it until we prove otherwise.

Title: Re: Formula for getting prime number?
Post by: Munchor on January 31, 2011, 08:56:16 am

Quote from: Galandros on January 30, 2011, 05:44:59 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:25:15 pm

Does it exist, if it does, can you tell me?(I need it to do mah APCS Homework D: )

No, there isn't any (known) formula to get the sequence of primes. But I don't know if it was proven mathematically that there is not such formula.
The difficulty to crack RSA depends on being hard to find primes and the interest on primes comes also from this.

There are formulas that give asymptotically the average of number of primes in an interval or probability of a random number being prime. See more in:
http://en.wikipedia.org/wiki/Prime_number_theorem

Wait a minute... I can code a program that gets all prime numbers in a second.

Title: Re: Formula for getting prime number?
Post by: Galandros on January 31, 2011, 09:24:10 am

Quote from: Scout on January 31, 2011, 08:56:16 am

Quote from: Galandros on January 30, 2011, 05:44:59 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:25:15 pm

Does it exist, if it does, can you tell me?(I need it to do mah APCS Homework D: )

No, there isn't any (known) formula to get the sequence of primes. But I don't know if it was proven mathematically that there is not such formula.
The difficulty to crack RSA depends on being hard to find primes and the interest on primes comes also from this.

There are formulas that give asymptotically the average of number of primes in an interval or probability of a random number being prime. See more in:
http://en.wikipedia.org/wiki/Prime_number_theorem

Wait a minute... I can code a program that gets all prime numbers in a second.

For RSA we are talking of numbers with hundreds of decimal digits.

Title: Re: Formula for getting prime number?
Post by: Munchor on January 31, 2011, 09:27:14 am

Quote from: Galandros on January 31, 2011, 09:24:10 am

Quote from: Scout on January 31, 2011, 08:56:16 am

Quote from: Galandros on January 30, 2011, 05:44:59 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:25:15 pm

Does it exist, if it does, can you tell me?(I need it to do mah APCS Homework D: )

No, there isn't any (known) formula to get the sequence of primes. But I don't know if it was proven mathematically that there is not such formula.
The difficulty to crack RSA depends on being hard to find primes and the interest on primes comes also from this.

There are formulas that give asymptotically the average of number of primes in an interval or probability of a random number being prime. See more in:
http://en.wikipedia.org/wiki/Prime_number_theorem

Wait a minute... I can code a program that gets all prime numbers in a second.

For RSA we are talking of numbers with hundreds of decimal digits.

decimal! I thought only integers would take part of such function.

Title: Re: Formula for getting prime number?
Post by: Galandros on January 31, 2011, 09:42:05 am

Quote from: Scout on January 31, 2011, 09:27:14 am

Quote from: Galandros on January 31, 2011, 09:24:10 am

Quote from: Scout on January 31, 2011, 08:56:16 am

Quote from: Galandros on January 30, 2011, 05:44:59 pm

Quote from: yeongJIN_COOL on January 07, 2011, 04:25:15 pm

Does it exist, if it does, can you tell me?(I need it to do mah APCS Homework D: )

No, there isn't any (known) formula to get the sequence of primes. But I don't know if it was proven mathematically that there is not such formula.
The difficulty to crack RSA depends on being hard to find primes and the interest on primes comes also from this.

There are formulas that give asymptotically the average of number of primes in an interval or probability of a random number being prime. See more in:
http://en.wikipedia.org/wiki/Prime_number_theorem

Wait a minute... I can code a program that gets all prime numbers in a second.

For RSA we are talking of numbers with hundreds of decimal digits.

decimal! I thought only integers would take part of such function.

The number of decimal digits representation of the integer. It is true that it is always integer in this sort of things. Don't confuse "decimal type" with its "decimal representation".
The RSA public key is 1024-bits to 2048-bits in current days. In general, people understand more the quantities when you mention it in decimal than in binary bits.
You barely can imagine the monstrosity of the prime factors...