This code has been declared by its author to be Public Domain code.
Download source code | | Prime Number Finder by GIB3D | 2008 |
| |
|
Edit: There are now two prime functions
Prime() is fast
Prime2() is fast, just not as fast as Prime() |
Graphics 500,700,1,2
;For n = 0 To 21
; Text 0,n*30,"n = " + n
; If Prime(n) = 1
; Text 20,(n*30)+10,"Is n("+n+") a prime number? Yes"
; Else
; Text 20,(n*30)+10,"Is n("+n+") a prime number? No"
; EndIf
;Next
For n = 1 To 100000
If Prime(n) = 1
Print n
EndIf
If KeyHit(1) End
Next
WaitKey()
Function Prime(prime%)
For divide = 2 To Sqr(prime)
If prime Mod divide = 0
Return False
EndIf
Next
If prime => 2
Return True
Else
Return False
EndIf
End Function
Function Prime2(prime%)
Local Not_Primes% ; If the givin number is prime Ex: 5
; then it will only return 2 Whole Numbers when it's divided by all of the numbers before it : 1 to 5
; Everytime it returns a Whole Number, then Not_Primes = Not_Primes + 1
; A prime number should only have 2 Whole Numbers and the rest are ones with a decimal point.
; If Not_Primes only = 2 at the end, then the number is a prime number
For divide% = 1 To prime
divided_prime# = Float(prime)/divide
If divided_prime = Int(divided_prime)
Not_Primes = Not_Primes + 1
EndIf
Next
If Not_Primes = 2
Return True
Else
Return False
EndIf
End Function |
Comments |
You only have to divide it by up to half of itself. A number can't possibly be divisible by any more than half of itself.
|
|
in fact, you only have to check up to its square root - if n = a*b, where a>sqr(n), then clearly b<sqr(n).
|
|
TaskMaster: I have to to divide all of those numbers or else it would include 1 as a prime number and it's not because I'm seeing if there are exactly 2 Whole Numbers.
Warpy: I think it would end up the same as TaskMaster's way.
|
|
Though not always as elegant, simply checking for pathological cases like 1 here is often a lot faster. Also, checking those cases before running the more intensive code may be better.
|
Code Archives Forum
