0

Необходимо проверить, является ли число простым используя функцию.
Решил вот так, но работает не до конца правильно. Не могу отловить причину...

int prime(unsigned int num {
    for ( int i = 2; i * i <= num; i++ ) {
        if ( num % i == 0 ) {
            return 0;
        }
    }
    return 1;
}
7
  • «работает не до конца правильно» следует понимать как «не компилируется»?
    – VladD
    28 июн 2013 в 17:22
  • 2
    Если добавить пропущенную скобку, проблема будет в возможном переполнении при возведении в квадрат. Знаковое переполнение является undefined behaviour по стандарту.
    – VladD
    28 июн 2013 в 17:24
  • раобтает она у вас правильно, только после unsigned int num вы забыли закрывающую круглую скобку. Ну и еще стоит отметить неоптимальность алгоритма. Но в целом верно
    – DreamChild
    28 июн 2013 в 17:25
  • @DreamChild: А если num == MAXINT? Или простое число чуть меньше MAXINT?
    – VladD
    28 июн 2013 в 17:28
  • @VladD я даже более того скажу - тут достаточно корня из MAXINT плюс один. Хотя, чего уж там - изначально возведение n в квадрат я не заметил.
    – DreamChild
    28 июн 2013 в 17:33

4 ответа 4

1
bool is_prime(unsigned p) {

    if ( p < 2 ) return false;
    if ( p == 2 ) return true;
    if ( p%2 == 0 ) return false;

    double limit = sqrt(p);

    for (unsigned i=3; i<=limit; i+=2) {
        if ( (p % i) == 0 ) return false;
    }

    return true;
}
3
  • У Вас маленькая ошибочка - 2-ка это тоже простое число.
    – avp
    30 июн 2013 в 17:57
  • Да, Вы правы
    – nullptr
    30 июн 2013 в 21:44
  • @nullptr, а Вы тестируете, что пишете? -- Теперь поменяйте порядок первых if-ов. 2-ка ведь четная и для нее сработает первый if, возвращающий false.
    – avp
    30 июн 2013 в 21:56
0

Небольшая оптимизация. Сначала проверьте num на равно 2 (простое), меньше 2 и num четное число (не простые). Затем можно перебирать только нечетные:

uint32_t i, lim = sqrt(num) + 1;
for (i = 3; i < lim; i += 2)
  if (num % i == 0)
    return 0;

return 1;

Глянул асм. код. Несмотря на -O3 чуть лучше так:

 uint32_t i, lim = ((uint32_t)sqrt(num)) + 1;

--

@VladD, решето не для этой задачи. Решето - это поиск всех простых (задано их количество). Здесь же требуется проверить только одно число.

0

Вот решение на C++ хотите переписывайте на СИ источник: решето Аткина

#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;
}
10
  • @perfect, что произойдет если проверить число 4000000001?
    – avp
    1 июл 2013 в 8:12
  • у меня вывело что число 4000000001 - простое
    – perfect
    1 июл 2013 в 10:26
  • 2
    А теперь запускаем проверку на [WolframAlpha][1] и получаем, что 4000000001 = 47 * 127 * 670129, то есть нифига не простое. [1]: wolframalpha.com/input/?i=4000000001
    – fori1ton
    1 июл 2013 в 10:48
  • 1
    @perfect, код @nullptr (естественно поправлен, как в моем комментарии к нему) как раз работает. А вот Ваш код сообщает что число 4000000005 простое, что (даже без вольфрама) очевидно не так. (4000000005 прекрасно делится на 5). Где-то у Вас для чисел больше 2^31 ошибочка закралась.
    – avp
    1 июл 2013 в 11:24
  • 1
    @renegator, так напишите (например в "исследованиях"). @perfect, замените в программе все int на unsigned int. И проверяйте (если дождетесь...).
    – avp
    1 июл 2013 в 13:08
0

Согласен с renegator. Для VBA (возможно кому-то нужно) строковая функция, возвращающая все квадраты простых чисел

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.