Задание 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\)