using System;
using System.Collections.Generic;
public class Test
{
public static List<int> get_primes (int n) {
// is_prime[i] == true, если i -- простое число
bool[] is_prime = new bool[n+1];
for (int i = 2; i <= n; ++i) is_prime[i] = true;
// primes будет содержать все простые числа на отрезке от 1 до n
List<int> primes = new List<int>();
// Алгоритм Решето Эратосфена
for (int i=2; i<=n; ++i)
if (is_prime[i]) {
primes.Add(i);
if (i * i <= n)
for (int j=i*i; j<=n; j+=i)
is_prime[j] = false;
}
return primes;
}
public static void Main()
{
List<int> primes = get_primes(20);
Console.WriteLine(string.Join(", ", primes));
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKCnB1YmxpYyBjbGFzcyBUZXN0CnsKCXB1YmxpYyBzdGF0aWMgTGlzdDxpbnQ+IGdldF9wcmltZXMgKGludCBuKSB7CgkJLy8gaXNfcHJpbWVbaV0gPT0gdHJ1ZSwg0LXRgdC70LggaSAtLSDQv9GA0L7RgdGC0L7QtSDRh9C40YHQu9C+CgkJYm9vbFtdIGlzX3ByaW1lID0gbmV3IGJvb2xbbisxXTsKCQlmb3IgKGludCBpID0gMjsgaSA8PSBuOyArK2kpIGlzX3ByaW1lW2ldID0gdHJ1ZTsKCQkvLyBwcmltZXMg0LHRg9C00LXRgiDRgdC+0LTQtdGA0LbQsNGC0Ywg0LLRgdC1INC/0YDQvtGB0YLRi9C1INGH0LjRgdC70LAg0L3QsCDQvtGC0YDQtdC30LrQtSDQvtGCIDEg0LTQviBuCgkJTGlzdDxpbnQ+IHByaW1lcyA9IG5ldyBMaXN0PGludD4oKTsKCQkvLyDQkNC70LPQvtGA0LjRgtC8INCg0LXRiNC10YLQviDQrdGA0LDRgtC+0YHRhNC10L3QsAoJCWZvciAoaW50IGk9MjsgaTw9bjsgKytpKQoJCSAgICBpZiAoaXNfcHJpbWVbaV0pIHsKCQkgICAgCXByaW1lcy5BZGQoaSk7CgkJICAgICAgICBpZiAoaSAqIGkgPD0gbikKCQkgICAgICAgICAgICBmb3IgKGludCBqPWkqaTsgajw9bjsgais9aSkKCQkgICAgICAgICAgICAgICAgaXNfcHJpbWVbal0gPSBmYWxzZTsKCQkgICAgfQoJCXJldHVybiBwcmltZXM7Cgl9CgkKCXB1YmxpYyBzdGF0aWMgdm9pZCBNYWluKCkKCXsKCQlMaXN0PGludD4gcHJpbWVzID0gZ2V0X3ByaW1lcygyMCk7CgkJQ29uc29sZS5Xcml0ZUxpbmUoc3RyaW5nLkpvaW4oIiwgIiwgcHJpbWVzKSk7Cgl9Cn0K