static void Main(string[] args) { List<int> numbers = ShowPrime(); Int32.TryParse(Console.ReadLine(), out int count); List<string> limits = new List<string>(); //считываем лимиты for (int i = 0; i < count; i++) { limits.Add(Console.ReadLine()); } for (int i = 0; i < count; i++) { var limitgroup = limits[i].Split(' '); var start = numbers.FindLastIndex(x => x <= Int32.Parse(limitgroup[0])); var end = numbers.FindLastIndex(x => x <= Int32.Parse(limitgroup[1])); if (start < 0) start = 0; for (int j = start; j <= end; j++) { Console.WriteLine(numbers[j]); } } } public static List<int> ShowPrime() { List<int> numbers = new List<int>(); bool isPrime; for (int i = 2; i <= 32000; i++) { isPrime = true; if (i > 10) { if (i % 10 == 5 || i % 2 == 0) continue; } // ускоритель for (int j = 2; j < (int)(Math.Sqrt(i) + 1); j++) { if (j * j - 1 > i) { isPrime = false; break; } if (i % j == 0 && i > 2) { isPrime = false; break; } } if (isPrime) numbers.Add(i); } return numbers; }
I get a wrong answear?but i check in list i have exatly only prime numbers? I dont understand which test is failed
PRIME1
I gave it
1 100 130
and the first prime it printed was 97.
Ok i fix this path var start = numbers.FindIndex(0,x=> x>=Int32.Parse(limitgroup[0])) but i again get a WA
Try this:
1 1009000 1100000
When I run it, the output starts with 2, 3, 5… 31991
edit: also, I don’t know whether this would cause WA for this problem, but you don’t print the blank line between test cases.
Ok I’am rise up limit for 10000000 but now i get TLE , may be C# is not fast language for this solution ? Because i check it in VS2017 and it take to calculating near 6 seconds to prepare list of prime number from 2…10000000 May be you advise me something what make calculation faster ?
I also started with a sieve, and got TLE. You either need a faster sieve or a different algorithm. Miller Rabin worked for me.