結果
問題 | No.713 素数の和 |
ユーザー | vwxyz |
提出日時 | 2022-09-07 04:12:52 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 3,059 bytes |
コンパイル時間 | 87 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-11-22 04:58:59 |
合計ジャッジ時間 | 1,250 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
11,904 KB |
testcase_01 | AC | 41 ms
12,032 KB |
testcase_02 | AC | 41 ms
11,904 KB |
testcase_03 | AC | 41 ms
11,904 KB |
testcase_04 | AC | 41 ms
11,904 KB |
testcase_05 | AC | 41 ms
11,904 KB |
testcase_06 | AC | 41 ms
12,160 KB |
testcase_07 | AC | 42 ms
11,904 KB |
testcase_08 | AC | 42 ms
11,904 KB |
ソースコード
import bisectimport copyimport decimalimport fractionsimport heapqimport itertoolsimport mathimport randomimport sysimport timefrom collections import Counter,deque,defaultdictfrom functools import lru_cache,reducefrom heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_maxdef _heappush_max(heap,item):heap.append(item)heapq._siftdown_max(heap, 0, len(heap)-1)def _heappushpop_max(heap, item):if heap and item < heap[0]:item, heap[0] = heap[0], itemheapq._siftup_max(heap, 0)return itemfrom math import gcd as GCDread=sys.stdin.readreadline=sys.stdin.readlinereadlines=sys.stdin.readlineswrite=sys.stdout.writeclass Prime:def __init__(self,N):assert N<=10**8self.smallest_prime_factor=[None]*(N+1)for i in range(2,N+1,2):self.smallest_prime_factor[i]=2n=int(N**.5)+1for p in range(3,n,2):if self.smallest_prime_factor[p]==None:self.smallest_prime_factor[p]=pfor i in range(p**2,N+1,2*p):if self.smallest_prime_factor[i]==None:self.smallest_prime_factor[i]=pfor p in range(n,N+1):if self.smallest_prime_factor[p]==None:self.smallest_prime_factor[p]=pself.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]]def Factorize(self,N):assert N>=1factors=defaultdict(int)if N<=len(self.smallest_prime_factor)-1:while N!=1:factors[self.smallest_prime_factor[N]]+=1N//=self.smallest_prime_factor[N]else:for p in self.primes:while N%p==0:N//=pfactors[p]+=1if N<p*p:if N!=1:factors[N]+=1breakif N<=len(self.smallest_prime_factor)-1:while N!=1:factors[self.smallest_prime_factor[N]]+=1N//=self.smallest_prime_factor[N]breakelse:if N!=1:factors[N]+=1return factorsdef Divisors(self,N):assert N>0divisors=[1]for p,e in self.Factorize(N).items():pow_p=[1]for _ in range(e):pow_p.append(pow_p[-1]*p)divisors=[i*j for i in divisors for j in pow_p]return divisorsdef Is_Prime(self,N):return N==self.smallest_prime_factor[N]def Totient(self,N):for p in self.Factorize(N).keys():N*=p-1N//=preturn Ndef Mebius(self,N):fact=self.Factorize(N)for e in fact.values():if e>=2:return 0else:if len(fact)%2==0:return 1else:return -1N=int(readline())P=Prime(N)ans=sum(P.primes)print(ans)