結果
問題 | No.843 Triple Primes |
ユーザー |
![]() |
提出日時 | 2019-06-28 21:38:12 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,027 ms / 2,000 ms |
コード長 | 1,050 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 28,800 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 13:52:58 |
合計ジャッジ時間 | 20,176 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 42 |
ソースコード
#include <stdio.h> #include <stdbool.h> typedef long long ll; bool is_prime[500005]; ll list_prime[500005]; ll calc_prime(ll n); int main() { ll n; ll m; ll ans = 0; scanf("%lld", &n); m = calc_prime(n); for (ll i = 0; i < m; i++) { for (ll j = i; j < m; j++) { ll p = list_prime[i]; ll r = list_prime[j]; ll q = r * r - p; if (q >= 0 && q <= n && is_prime[q]) { if (i == j) { ans++; } else { ans += 2; } } } } printf("%lld\n", ans); return 0; } ll calc_prime(ll n) { ll cnt = 0; for (ll i = 2; i <= n; i++) { is_prime[i] = true; } for (ll i = 2; i <= n; i++) { if (is_prime[i]) { list_prime[cnt] = i; cnt++; for (ll j = i + i; j <= n; j += i) { is_prime[j] = false; } } } return cnt; }