Euler Solution 97

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 97

There is a large prime number (2357207 digits) given by: 28433 × 27830457 + 1, find the last ten digits of this prime.

Lisp by SanguineV

Runtime: 2.094 seconds (on aglaope)

; Define a function to multiply a number "n" by 2^8, "p" times modulo some "m"
(define (powMod n p m)
  (if (= 0 p)
  n
  (powMod (modulo (* n 256) m) (- p 1) m)))

; Given 2^7830457 == 2x256^978807 == 2x(2^8)^978807, use this below, then multiply by 
; 28433, add one and display the last 10 digits.
(begin (display (modulo (+ (* 28433 (powMod 2 978807 10000000000)) 1) 10000000000)) (newline))
(exit)


Python by Althalus

Runtime: Originally, 12 seconds. After implementing an improvement stolen from Thomas's solution: 2.01 seconds

# Original code, before I saw Thomas's solution.
#n=2;
#for i in xrange(7830456):
#    if n / 10000000000: n = n % 10000000000
#    n *= 2

# Stealing an optomisation from Thomas...(2^7830457 == 2x256^978807)
n=2*256;
for i in xrange(978806):
    if n / 10000000000: n = n % 10000000000
    n *= 256 

n=(n * 28433) + 1 
print n % 10000000000
Personal tools