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

Просмотры: 247
Изменено: 24 ноября 2024

Среди целых чисел, принадлежащих числовому отрезку \([125697; \,\, 190234]\), найдите числа, которые представляют собой произведение двух различных простых делителей. Запишите в ответе количество таких чисел и максимальное их них.

Решение:

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

primes = sieve(190234)
a = []

for x in range(125697, 190235):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            sec_div = x // i
            if i in primes and i != sec_div and sec_div in primes:
                a.append(x)
            break

print(len(a), max(a))

Java


import java.util.ArrayList;

public class EGE2599 {

    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(190234);
        ArrayList<Integer> a = new ArrayList<Integer>();
        for(int i = 125697; i < 190235; i++) {
            for(int j = 2; j < (int) Math.sqrt(i) + 1; j++) {
                if(i % j == 0) {
                    int sec_div = i / j;
                    if(primes.contains(j) && j != sec_div && primes.contains(sec_div)) {
                        a.add(i);
                    }
                    break;
                }
            }
        }
        int max_el = 125697;
        int sz = a.size();
        for(int i = 0; i < sz; i++) {
            if (a.get(i) > max_el) {
                max_el = a.get(i);
            }
        }
        System.out.println(sz + " " + max_el);
    }
}

Ответ: \(14047 \,\, 190231\)