Member Avatar for weIIet

hi all

i have a homework for Lehmann primality test and i have to know very big numbers as big as x**(2**128)

python is enough for 2**128 but when numbers bigger than it don't do it

my teacher python has a structure for it and i didn't find it for 2 days

thanks

  • 4 Contributors
  • 6 Replies
  • 2K Views
  • 21 Hours Discussion Span
  • Latest Post Latest Post by Thisisnotanid
Member Avatar for TrustyTony

decimal module has suppport of very long and accurate numbers, but I am not sure if it is enough for such extreme case. Usually you can find ways to work on powers with modulo, standard python pow supports second argument for modulo.

Member Avatar for weIIet 
def mod_al(p,a):
	r=1
	c=(p-1)/2
	i=1
	while i<c+1:
		r=(r*a) %p
		i=i+1
	return r


p=input("give me number\n")
a=2
mod=mod_al(p,a)

if mod==1 or mod==p-1:
	print "this number can be prime"
else:
	print "this number don't prime"

this is my program maybe you can find a solution
it works but when numbers very big such as 2**50 it don't

Edited by weIIet because: n/a
Member Avatar for woooee

2**218 = 421249166674228746791672110734681729275580381602196445017243910144 and
2**50 = 1125899906842624
Either one is going to take a long time. As Tony said you should be using the decimal module.

this is my program maybe you can find a solution
it works but when numbers very big such as 2**50 it don't

Not unless there is a mind reader here who can intuit what "it don't" means. I don't think any one is going to waste hours running the code through bigger and bigger numbers until they find out what "it don't" means.

Edited by woooee because: n/a
Member Avatar for TrustyTony

The time spent installing pypy1.8 to work faster with Mersenne primes, could be time well spent: http://pypy.org/download.html

Member Avatar for Thisisnotanid

Search for "prime number python" on DaniWeb; the site has a number of posts and snippets concerning primality testers. I specifically remember one which is useful for very large numbers, but it is probablistic: http://www.daniweb.com/software-development/python/threads/334159 (Look for vegaseat's answer at the end). Also a healthy google search on prime numbers should prove helpful.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.