본문 바로가기

프로그래밍/알고리즘

[Project Euler 123] (p-1)^n + (p+1)^n % p^2

반응형
http://projecteuler.net/index.php?section=problems&id=123

pn 이 n번째 소수 ( 2, 3, 5, 7, 11, ..., )이고, r이 (pn1)n + (pn+1)n 를 pn2으로 나눈 나머지라고 하자.

예를 들어, n = 3, p3 = 5 이고, 43 + 63 = 280 5 mod 25 이다.

이 나머지가 109을 넘는 가장 작은 n은 7037이다. 나머지가 1010을 넘는 가장 작은 n을 구하라.



#!/usr/bin/env python

# Project Euler Problem 123

def remainder0(p, n):
return ((p-1)**n + (p+1)**n)%(p*p)
def remainder(p, n):
'''
p is a prime.
returns
n n 2
(p-1) + (p+1) mod p
=
n-1 n 2
n p (-1) + (-1) + n p + 1 mod p
'''
if n%2 == 0:
fp = 2
else:
fp = 2*n*p
return fp % (p*p)

primes = [ 2, 3, 4, 5, 7, 11, 13, 17, 19, 23 ]

#for i in range(len(primes)):
# print remainder0(primes[i], i+1) == remainder(primes[i], i+1)

n = 10
candidate = 29
while True:
IsPrime = False
for p in primes:
if p*p > candidate:
# print candidate
IsPrime = True
break
if candidate%p == 0:
break
if IsPrime:
if remainder(candidate, n) > 10**10:
print n, candidate
break
primes.append(candidate)
n+=1
candidate+=1




728x90