#include <iostream>
#include <vector>
using namespace std;
bool is_prime(unsigned int num){
int limit = num;
int sqr_lim;
vector<bool> is_prime_f(num + 10);
int x2, y2;
int i, j;
int n;
// Инициализация решета
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime_f[i] = false;
is_prime_f[2] = true;
is_prime_f[3] = true;
// Предположительно простые - это целые с нечетным числом
// представлений в данных квадратных формах.
// x2 и y2 - это квадраты i и j (оптимизация).
x2 = 0;
for (i = 1; i <= sqr_lim; i++) {
x2 += 2 * i - 1;
y2 = 0;
for (j = 1; j <= sqr_lim; j++) {
y2 += 2 * j - 1;
n = 4 * x2 + y2;
if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
is_prime_f[n] = !is_prime_f[n];
// n = 3 * x2 + y2;
n -= x2; // Оптимизация
if ((n <= limit) && (n % 12 == 7))
is_prime_f[n] = !is_prime_f[n];
// n = 3 * x2 - y2;
n -= 2 * y2; // Оптимизация
if ((i > j) && (n <= limit) && (n % 12 == 11))
is_prime_f[n] = !is_prime_f[n];
}
}
// Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for (i = 5; i <= sqr_lim; i++) {
if (is_prime_f[i]) {
n = i * i;
for (j = n; j <= limit; j += n) {
is_prime_f[j] = false;
}
}
}
// Вывод списка простых чисел в консоль.
//printf("2, 3, 5");
if ((i == 2) || (i == 3) || (i == 5))
return true;
for (i = 6; i <= limit; i++) { // добавлена проверка делимости на 3 и 5. В оригинальной версии алгоритма потребности в ней нет.
if ((is_prime_f[i]) && (i % 3 != 0) && (i % 5 != 0)){
//printf(", %d", i);
if (i == num)
return true;
}
}
return 0;
}
int main(int argc, char* argv[]){
if (is_prime(983)){
cout << "prime" << endl;
} else {
cout << "not prime" << endl;
}
return 0;
}
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Виртуальный выделенный сервер (VDS) становится отличным выбором
Помогите пожалуйста создать алгоритм реализации хеш-функции и реализовать его на С++
Собственно то, что я сейчас понимаю: Необходимо написать драйвер для HDD (Для устройства, а не файловой системе), тк
Вдохновленный этим вопросом Bit hack to generate all integers with a given number of 1s интересует, а возможно ли пропускать в генерации значений содержащих определенный...
Как закрыть клиентское соединение средствами библиотеки libevent (на с++) после получения ответа от сервера, чтобы файловый дескриптор используемый...