Задание 25. Информатика. ЕГЭ. Поляков-2590

Python

def sieve(N):
    a = [1]*(N+1)

    a[0] = 0
    a[1] = 0

    for x in range(2, int(N**0.5) + 1):
        if a[x]:
            for i in range(x**2, N+1, x):
                a[i] = 0
                
    primes = []
    for x in range(2, N+1):
        if a[x]:
            primes.append(x)
    
    return primes

print(len(sieve(3577000)))

Java

import java.util.ArrayList;

public class EGE2590 {

    static ArrayList<Integer> Sieve(int N) {
        int a[] = new int[N];
        a[0] = 0;
        a[1] = 0;
        for(int i = 0; i < N; i++) {
            a[i] = 1;
        }
        for(int i = 2; i < (int) Math.sqrt(N) + 1; i++) {
            if(a[i] == 1) {
                for(int j = i*i; j < N; j += i) {
                    a[j] = 0;
                }
            }
        }
        ArrayList<Integer> primes = new ArrayList<Integer>();
        for(int i = 2; i < N; i++) {
            if(a[i] == 1) {
                primes.add(i);
            }
        }
        return primes;

    }
    public static void main(String argv[]) {
        ArrayList<Integer> primes = Sieve(3577000);
        System.out.println(primes.size());
    }
}

Ответ: 255203