Author Topic: Formula for getting prime number?  (Read 17921 times)

0 Members and 1 Guest are viewing this topic.

Offline Yeong

  • Not a bridge
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3739
  • Rating: +278/-12
  • Survivor of Apocalypse
    • View Profile
Formula for getting prime number?
« 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: )
Sig wipe!

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Formula for getting prime number?
« Reply #1 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?


Offline Yeong

  • Not a bridge
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3739
  • Rating: +278/-12
  • Survivor of Apocalypse
    • View Profile
Re: Formula for getting prime number?
« Reply #2 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;
}
« Last Edit: January 07, 2011, 04:31:10 pm by yeongJIN_COOL »
Sig wipe!

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Formula for getting prime number?
« Reply #3 on: January 07, 2011, 04:30:50 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;


Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Formula for getting prime number?
« Reply #4 on: January 07, 2011, 04:31:43 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

« Last Edit: January 07, 2011, 04:33:05 pm by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Formula for getting prime number?
« Reply #5 on: January 07, 2011, 04:32:22 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
« Last Edit: January 07, 2011, 04:32:57 pm by nemo »


Offline Yeong

  • Not a bridge
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3739
  • Rating: +278/-12
  • Survivor of Apocalypse
    • View Profile
Re: Formula for getting prime number?
« Reply #6 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
« Last Edit: January 07, 2011, 04:34:56 pm by yeongJIN_COOL »
Sig wipe!

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Formula for getting prime number?
« Reply #7 on: January 07, 2011, 04:35:07 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.


Offline Michael_Lee

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1019
  • Rating: +124/-9
    • View Profile
Re: Formula for getting prime number?
« Reply #8 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.
My website: Currently boring.

Projects:
Axe Interpreter
   > Core: Done
   > Memory: Need write code to add constants.
   > Graphics: Rewritten.  Needs to integrate sprites with constants.
   > IO: GetKey done.  Need to add mostly homescreen IO stuff.
Croquette:
   > Stomping bugs
   > Internet version: On hold until I can make my website less boring/broken.

Offline Hot_Dog

  • CoT Emeritus
  • LV12 Extreme Poster (Next: 5000)
  • *
  • Posts: 3006
  • Rating: +445/-10
    • View Profile
Re: Formula for getting prime number?
« Reply #9 on: January 09, 2011, 12:39:01 am »
It has been proven, by the way, that there is no largest prime number 8)

Offline z80man

  • Casio Traitor
  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 977
  • Rating: +85/-3
    • View Profile
Re: Formula for getting prime number?
« Reply #10 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.

List of stuff I need to do before September:
1. Finish the Emulator of the Casio Prizm (in active development)
2. Finish the the SH3 asm IDE/assembler/linker program (in active development)
3. Create a partial Java virtual machine  for the Prizm (not started)
4. Create Axe for the Prizm with an Axe legacy mode (in planning phase)
5. Develop a large set of C and asm libraries for the Prizm (some progress)
6. Create an emulator of the 83+ for the Prizm (not started)
7. Create a well polished game that showcases the ability of the Casio Prizm (not started)

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Formula for getting prime number?
« Reply #11 on: January 09, 2011, 03:46:50 pm »
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.
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.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Formula for getting prime number?
« Reply #12 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

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: Formula for getting prime number?
« Reply #13 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
« Last Edit: January 09, 2011, 06:45:46 pm by willrandship »

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Formula for getting prime number?
« Reply #14 on: January 09, 2011, 06:49:09 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.