Python Prime Number Checker

For the discussion of Perl, Python, Ruby, and PHP and other interpreted languages.

Python Prime Number Checker

Post by Arrexel on Sun Feb 22, 2009 3:09 pm
([msg=18415]see Python Prime Number Checker[/msg])

I thought this would be useful for RSA key generation and such, and I was also bored out of my tree.

Code: Select all

# Prime Number Checker by Alex "Arrexel" Reid
print "Prime Number Checker"
primenum = float(raw_input("Enter the number to check: "))

if primenum % 2 == 0:
    primehalf = primenum / 2
elif primenum % 2 != 0:
    primehalf = primenum / 2 + 0.5

primehalf = long(primehalf)
divisor = 2
prime = True

for x in range(primehalf):
    if primenum % divisor == 0:
        print int(primenum), "is not a prime number."
        prime = False
        break
    divisor += 1

if prime != False:
    print int(primenum), "is a prime number."


Add suggestions/improvements/comments.

-Arr
"I think there is a world market for maybe five computers."
Unverified Quote, 1945 - Thomas J. Watson, Founder of IBM
User avatar
Arrexel
New User
New User
 
Posts: 31
Joined: Fri Feb 13, 2009 7:44 pm
Location: Ontario, Canada
Blog: View Blog (0)


Re: Python Prime Number Checker

Post by Gangees on Sun Feb 22, 2009 7:26 pm
([msg=18441]see Re: Python Prime Number Checker[/msg])

I'm not much of a coder but from a mathematical point of view, it would be quicker to use the square root function instead of the primehalf that you use. Also you can check for divisibility by 2 in a seperate step, then set your divisor=3 at the start and increase by 2 instead (since you only need to check the odd numbers).

Code: Select all
# Prime Number Checker by Alex "Arrexel" Reid
print "Prime Number Checker"
primenum = float(raw_input("Enter the number to check: "))

if primenum % 2 == 0:
      print int(primenum), "is not a prime number."

primeroot=int(primenum**.5)
divisor = 3
prime = True

for x in range(primeroot):
    if primenum % divisor == 0:
        print int(primenum), "is not a prime number."
        prime = False
        break
    divisor += 2

if prime != False:
    print int(primenum), "is a prime number."


Hopefully this helps!
Gangees
New User
New User
 
Posts: 1
Joined: Sun Feb 22, 2009 7:09 pm
Blog: View Blog (0)


Re: Python Prime Number Checker

Post by Arrexel on Mon Feb 23, 2009 4:11 pm
([msg=18490]see Re: Python Prime Number Checker[/msg])

Ah, all good suggestions. We need more posts like that being made on these forums :)
"I think there is a world market for maybe five computers."
Unverified Quote, 1945 - Thomas J. Watson, Founder of IBM
User avatar
Arrexel
New User
New User
 
Posts: 31
Joined: Fri Feb 13, 2009 7:44 pm
Location: Ontario, Canada
Blog: View Blog (0)


Re: Python Prime Number Checker

Post by TheMindRapist on Tue Feb 24, 2009 7:24 pm
([msg=18596]see Re: Python Prime Number Checker[/msg])

You can optimize it even further by pregenerating a list of prime numbers, and only checking if the input is divisible by prime numbers.
Image
User avatar
TheMindRapist
Contributor
Contributor
 
Posts: 585
Joined: Mon Apr 14, 2008 4:57 pm
Blog: View Blog (0)


Re: Python Prime Number Checker

Post by Arrexel on Wed Feb 25, 2009 3:20 pm
([msg=18663]see Re: Python Prime Number Checker[/msg])

Ahh, good idea as well. Just so have it, that I generated the first 100,000 primes last night with a script I made. As a matter of fact, I was about to post it before I saw a reply here :)

I bet it could use improvements, too.
"I think there is a world market for maybe five computers."
Unverified Quote, 1945 - Thomas J. Watson, Founder of IBM
User avatar
Arrexel
New User
New User
 
Posts: 31
Joined: Fri Feb 13, 2009 7:44 pm
Location: Ontario, Canada
Blog: View Blog (0)


Re: Python Prime Number Checker

Post by Defience on Sat Feb 28, 2009 1:18 pm
([msg=18887]see Re: Python Prime Number Checker[/msg])

Yeah, like TheMindRapist said you could have a list of primes and check against that list. Maybe something like this which could be expanded on with some 'if' statements but you get the idea:

>>> primes=[2,3,5,7,11,13,17,19,23]
>>> str_digits="23"
>>> str_prime=''.join([c for c in str_digits if int(c) in (primes)])
>>> str_prime
'23'
User avatar
Defience
Addict
Addict
 
Posts: 1277
Joined: Thu Jun 12, 2008 3:16 pm
Blog: View Blog (0)



Return to Interpreted Languages

Who is online

Users browsing this forum: No registered users and 0 guests