結果
問題 | No.371 ぼく悪いプライムじゃないよ |
ユーザー |
![]() |
提出日時 | 2016-05-14 16:48:01 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 263 ms / 1,000 ms |
コード長 | 1,008 bytes |
コンパイル時間 | 339 ms |
コンパイル使用メモリ | 6,784 KB |
実行使用メモリ | 10,144 KB |
最終ジャッジ日時 | 2024-12-30 18:12:45 |
合計ジャッジ時間 | 4,020 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
import math L,H=map(int,raw_input().split()) upperBound = 100001 isPrime=[True for i in range((upperBound-3)/2+1)] for i in range((int(math.sqrt(upperBound-3))-3)/2+1): # k*k = (2i+3)^2 <= upperBound-3 if isPrime[i]: k = i+i+3 # this is prime number # false out non_prime number from k*k # k*k = 4i^2+12i+9 = 2*(2i^2+6i+3)+3 # k*(k+1) = 2*(2i^2+6i+3)+3 + 2i+3 ... even number. skip # k*(k+2) = 2*(2i^2+6i+3+k)+3 non_prime = k*(i+1)+i for j in range(non_prime,(upperBound-3)/2+1,k): isPrime[j]=False primes = [2] + [i+i+3 for i in range((upperBound-3)/2+1) if isPrime[i]==True] primes.reverse() for i,p in enumerate(primes): #print p if H/p < p: continue for c in range((H/p)*p, L-1, -p): if c==p: break ok = True for j in range(i+1,len(primes)): q=primes[j] if c%q==0: ok=False break if ok: print c exit()