Мобильная версияОписание задачи
Простое число – это целое положительное число X, имеющее ровно два различных делителя: 1 и X. Первые несколько простых целых чисел — 2, 3, 5, 7, 11 и 13.
Полупростое — это натуральное число, которое является произведением двух (не обязательно различных) простых чисел. Первые несколько полупростых чисел — 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.
Вам даны два непустых массива P и Q, каждое из которых состоит из M целых чисел. Эти массивы представляют собой запросы о количестве полупростых чисел в указанных диапазонах.
Запрос K требует, чтобы вы нашли количество полупростых чисел в диапазоне (P[K], Q[K ]), где 1 ≤ P[K] ≤ Q[K] ≤ N.
Напишите эффективный алгоритм для следующих предположений:
- N — целое число в пределах диапазона [1..50,000];
- M — целое число в диапазоне [1..30,000];
- каждый элемент массивов P, Q целое число в диапазоне [1..N];
P ≤ Q.
Мое решение
Мой текущий результат: 66%, и проблема заключается в производительности для большого набора данных:
- большой случайный результат, длина = ~ 30 000
- все максимальные диапазоны
Тест показывает, что это должно занять около 2 секунд, но мое решение занимает более 7 секунд.
Это мое текущее решение
Код: Выделить всё
class Solution {
private static List getPrimes(int max) {
List primes = new ArrayList(max / 2);
for (int i = 0; i < max; i++)
if (isPrime(i))
primes.add(i);
return primes;
}
private static boolean isPrime(int val) {
if (val
Подробнее здесь: [url]https://stackoverflow.com/questions/53902549/count-the-semiprime-numbers-in-the-given-range-a-b[/url]