結果
問題 | No.713 素数の和 |
ユーザー |
![]() |
提出日時 | 2020-05-06 19:38:05 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 6,367 bytes |
コンパイル時間 | 2,109 ms |
コンパイル使用メモリ | 117,432 KB |
実行使用メモリ | 27,008 KB |
最終ジャッジ日時 | 2024-07-03 09:05:52 |
合計ジャッジ時間 | 2,949 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections;using System.Collections.Generic;using System.IO;using System.Linq;class Program{static void Main(string[] args){var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };Console.SetOut(sw);Solve();Console.Out.Flush();}static void Solve(){var N = sc.ReadInt();var se = new SieveOfEratosthenes(N);var ans = 0;for (int i = 2; i <= N; i++){if (se.IsPrime(i)) ans += i;}Console.WriteLine(ans);}class SieveOfEratosthenes{public int[] Table;public SieveOfEratosthenes(int max){CreateTable(max);}// n以下の数について、最小素因数を記録した表を生成するprivate void CreateTable(int n){Table = Enumerable.Range(0, n + 1).ToArray();if (n <= 3) return;// 2の倍数の最小素因数は2for (int i = 2; i <= n; i += 2) Table[i] = 2;// 3以上の奇数について最小素因数を記録するfor (int p = 3; p * p <= n; p += 2){// 奇数pがp未満の数の倍数である場合は無視if (Table[p] < p) continue;// 素数pの倍数を記録for (int x = p; x <= n; x += p){Table[x] = p;}}}// 最小素因数表を使って素因数分解を行うpublic List<int> PrimeFactors(int n){var res = new List<int>();var now = n;while (Table[now] != now){res.Add(Table[now]);now /= Table[now];}res.Add(now);return res;}// 素因数を(p, 個数)のペアで返すpublic List<Tuple<int, int>> PrimeFactorsTup(int n){var prev = 0;var count = 0;var res = new List<Tuple<int, int>>();if (n <= 1) return res;foreach (var p in PrimeFactors(n)){if (prev != p){if (count > 0) res.Add(Tuple.Create(prev, count));count = 1;}else count++;prev = p;}res.Add(Tuple.Create(prev, count));return res;}// 素数判定public bool IsPrime(int n){return Table[n] == n;}}static Scanner sc = new Scanner();}class Scanner{string[] S = new string[0];int Index = 0;char[] Separators = new char[] { ' ' };public string Next(){if (this.Index < this.S.Length) return this.S[this.Index++];var line = "";while (line == "") line = Console.ReadLine();this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);if (this.S.Length == 0) return this.Next();this.Index = 0;return this.S[this.Index++];}public string ReadStr(){return this.Next();}public char ReadChar(){return this.Next()[0];}public int ReadInt(){return int.Parse(this.Next());}public uint ReadUInt(){return uint.Parse(this.Next());}public long ReadLong(){return long.Parse(this.Next());}public double ReadDouble(){return double.Parse(this.Next());}public Tuple<int, int> ReadTup(int add = 0){return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add);}public Tuple<long, long> ReadTupLong(int add = 0){return Tuple.Create(this.ReadLong() + add, this.ReadLong() + add);}public Tuple<int, int, int> ReadTup3(int add = 0){return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add);}public Tuple<int, int, int, int> ReadTup4(int add = 0){return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add);}public int[] ReadIntArray(int n){var array = new int[n];for (int i = 0; i < array.Length; i++){array[i] = this.ReadInt();}return array;}public long[] ReadLongArray(int n){var array = new long[n];for (int i = 0; i < array.Length; i++){array[i] = this.ReadLong();}return array;}public double[] ReadDoubleArray(int n){var array = new double[n];for (int i = 0; i < array.Length; i++){array[i] = this.ReadDouble();}return array;}public char[] ReadCharArray(int n){var array = new char[n];for (int i = 0; i < array.Length; i++){array[i] = this.ReadChar();}return array;}public string[] ReadStrArray(int n){var array = new string[n];for (int i = 0; i < array.Length; i++){array[i] = this.ReadStr();}return array;}public Tuple<long, long>[] ReadTupLongArray(int n, int add = 0){var array = new Tuple<long, long>[n];for (int i = 0; i < n; i++){array[i] = this.ReadTupLong(add);}return array;}public Tuple<int, int>[] ReadTupArray(int n, int add = 0){var array = new Tuple<int, int>[n];for (int i = 0; i < n; i++){array[i] = this.ReadTup(add);}return array;}public Tuple<int, int, int>[] ReadTup3Array(int n, int add = 0){var array = new Tuple<int, int, int>[n];for (int i = 0; i < n; i++){array[i] = this.ReadTup3(add);}return array;}public Tuple<int, int, int, int>[] ReadTup4Array(int n, int add = 0){var array = new Tuple<int, int, int, int>[n];for (int i = 0; i < n; i++){array[i] = this.ReadTup4(add);}return array;}}