結果
問題 | No.312 置換処理 |
ユーザー |
![]() |
提出日時 | 2017-04-13 19:32:29 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 343 ms / 2,000 ms |
コード長 | 1,549 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 50,816 KB |
最終ジャッジ日時 | 2024-11-15 12:15:39 |
合計ジャッジ時間 | 7,957 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
# coding: utf-8import mathN = int(input())def is_prime(num):if num < 2:return Falseif num == 2 or num == 3 or num == 5:return Trueif num % 2 == 0 or num % 3 == 0 or num % 5 == 0:return False# 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていくprime = 7step = 4num_sqrt = math.sqrt(num)while prime <= num_sqrt:if num % prime == 0:return Falseprime += stepstep = 6 - stepreturn Truedef make_prime_list(num):if num < 2:return []# 0のものは素数じゃないとするprime_list = [i for i in range(num + 1)]prime_list[1] = 0 # 1は素数ではないnum_sqrt = math.sqrt(num)for prime in prime_list:if prime == 0:continueif prime > num_sqrt:breakfor non_prime in range(2 * prime, num, prime):prime_list[non_prime] = 0return [prime for prime in prime_list if prime != 0]def solve():if N == 4:return 4if is_prime(N):return NN_sqrt = math.ceil(math.sqrt(N))primes = make_prime_list(N_sqrt)check_list = primes[:]for prime in primes:if prime * 2 > N_sqrt:breakcheck_list.append(prime * 2)check_list.sort()for num in check_list:if num == 2:continueif N % num == 0:return numif N % 2 == 0:return N // 2print(solve())