NewsForumsCodeLogsGallerySpecsSearch

Prime Finder

Blitz3D Forums/Blitz3D Programming/Prime Finder

GIB3D(Posted 2008) [#1]
Is there a function anyone has made that shows you prime numbers in some way or tells you whether a number is prime or not? I was just wondering because I just made one that works perfectly, but I'm only going to put it in the Code Archives if there's not already one.

The one that I saw in the archives is really long
http://blitzbasic.com/codearcs/codearcs.php?code=1888
but the one I made is way shorter and it works.

Hehe, it's been 1 hour so i'll take the "no replies" as a no.

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

WaitKey()

Function Prime(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
			If Float(prime)/divide = Int(Float(prime)/divide)
				Not_Primes = Not_Primes + 1
			EndIf
		Next
		
		If Not_Primes = 2
			Return True
				Else
					Return False
		EndIf
End Function



Ginger Tea(Posted 2008) [#2]
any chance it could brute force a search between
010203040507 and 444546474849
im only interested in any of these prime numbers as they are uk lotto combinations* :D

*providing they dont duplicate a ball that is ;)
ive searched for prime lists and all i get are wonky format data lists not human readable text files


Shambler(Posted 2008) [#3]
I remember you can use a sieve
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

You could miss out the divide by 1.


GIB3D(Posted 2008) [#4]
Ginger Tea: I put in 010203040507 my Prime function and it took about a minute for it to come up with "0", meaning it's not a prime number. So if you're looking for a lot of number that long, I guess you'd need a pretty fast computer. But it could work, I just don't see what primes have to do with lotto combinations... cheating... that's a huge waste of time?

Anyways, how would you be putting them in the Prime function? Like
Prime(010203040507)


or

Prime(01)
Prime(02)
Prime(03)
Prime(04)
Prime(05)
...



Buggy(Posted 2008) [#5]
Actually, you could streamline this much more by - as mentioned - not dividing by one (useless), as well as not going all the way up to the number.

If the number to be tested is n, then you only need to divide by numbers going up to the square root of n (otherwise you're repeating everything). And this way, once something divides evenly, you can return false and move on.

By the way, the Mod command works better here; it's not prime if prime Mod divide = 0.

So, our new code:
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

WaitKey()

Function Prime(prime%)
	
	Local Not_Primes% ; If the givin number is prime Ex: 5
			  ; then it will not divide evenly by anything between 2 and the square root of 5
					
	For divide = 2 To Sqr(prime)
		
		If prime Mod divide = 0
			
			Return False
				
		EndIf
			
	Next
		
	Return True
		
End Function


Probably could be optimized further, but I think that's much better, don't you?


Buggy(Posted 2008) [#6]
And, to prove the speed of this code, try this. It's quite fun!
Graphics 500,700,1,2

For n = 0 To 200000
		
	If Prime(n) = 1
	
		Print n
		
	EndIf

Next

WaitKey()

Function Prime(prime%)
	
	Local Not_Primes% ; If the givin number is prime Ex: 5
			  ; then it will not divide evenly by anything between 2 and the square root of five
					
	For divide = 2 To Sqr(prime)
		
		If prime Mod divide = 0
			
			Return False
				
		EndIf
			
	Next
		
	Return True
		
End Function



GIB3D(Posted 2008) [#7]
:O Cool, yours does go faster. I'll see what I can learn from this.


GIB3D(Posted 2008) [#8]
I changed that code so it doesn't return those numbers under 2 that AREN'T prime. That way I had my code at first didn't let it show the numbers that weren't prime, but it was a bit slow.

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



Ginger Tea(Posted 2008) [#9]
why?
well why not :D

out of all the 14 and a bit million lotto combinations* some of em might be prime numbers
some people pick birthdates or relevant sequences
im just curious as to what if any prime numer sets have come up

6 balls (excluding bonus ball) numbered between 1 and 49


Buggy(Posted 2008) [#10]
I'm almost positive it's loads faster (haven't tried it, but all of these computation-heavy programs almost always are) if we get rid of that Graphics command.