Заблокирован
1

Проверка числа на простоту

19.04.2015, 10:28. Показов 4002. Ответов 7
Метки нет (Все метки)

я реализовал вот так, но алгоритм очень долгий, мне надо проверять очень большое количество чисел (десятки тысяч) и он так надолго виснет что я так и не смог дождаться конца проверки, может можно сделать как то попроще его?

C++
1
2
3
4
5
6
7
8
9
10
bool IsPrime(unsigned long long value)
{
    if (value < 2)
        return false;
    int count = 0;
    for (unsigned long long i = 1; i <= value; i++)
        if (!(value % i))
            count++;
    return !(count > 2);
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.04.2015, 10:28
Ответы с готовыми решениями:

Проверка числа на простоту
Помогите написать программу которая проверяет простое число или нет.

Проверка числа на простоту
Дано натуральное число N, проверить, простое оно или нет. Увеличить его значение на натуральное...

Проверка числа на простоту
Написать программу, которая запрашивает массив натуральных чисел (ввод с клавиатуры), а затем...

Проверка на простоту числа
как мне сделать так, чтобы узнать простое является число или составное, не через bool, а как-нибудь...

7
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
19.04.2015, 10:37 2
Ты весь диапазон long long используешь? Может проще взять готовый список простых чисел и в нём искать?
0
Заблокирован
19.04.2015, 10:44  [ТС] 3
Цитата Сообщение от nmcf Посмотреть сообщение
Ты весь диапазон long long используешь?
да
Цитата Сообщение от nmcf Посмотреть сообщение
Может проще взять готовый список простых чисел и в нём искать?
а какая разница то? все равно получится точно такой же цикл с тем же числом проходов... я имею ввиду может можно кардинально по другому как то искать? ну там какие то условия проставить... чтобы не было таких здоровых циклов, ибо циклы - это время...
0
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
19.04.2015, 10:50 4
Поиск в упорядоченном массиве не может быть таким же сложным как деление числа на все меньшие.
Ну если весь диапазон, то, наверное, только так, как у тебя.
0
случайный прохожий
2227 / 1466 / 503
Регистрация: 20.07.2013
Сообщений: 4,147
19.04.2015, 10:52 5
Проверять можно не до value, а до квадратного корня этой величины.
Тогда, если count будет >= 2, то число не простое.
Цикл можно начинать с 2 (тогда условие для count станет другим: >= 1, я прав?). Начиная со значения i = 3 инкрементировать счетчик сразу на 2. После проверки на делимость на 5 не рассматривать делители, кратные 5 (т. е. оканчивающиеся на 0 и 5). И т. д. и т. п.
Вроде примерно так.
Если ошибаюсь, поправьте. Информацию из памяти взял (а она иногда дает сбои).
P.S.: можешь еще здесь Быстрая проверка натурального числа на простоту посмотреть.
0
Заблокирован
19.04.2015, 10:57  [ТС] 6
gunslinger, смотрел уже все эти темы ни один алгоритм не рабочий (в том числе и с корнем), просто берем и подставляем первое же составное число (например 4) и он все равно возвращает true...
0
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
19.04.2015, 11:02 7
Цитата Сообщение от gunslinger Посмотреть сообщение
не до value, а до квадратного корня этой величины
А не до value / 2?

И зачем вообще count? Почему не сразу return?
0
случайный прохожий
2227 / 1466 / 503
Регистрация: 20.07.2013
Сообщений: 4,147
19.04.2015, 19:16 8
Нет, до корня, причем, возможно, даже не включая его.
count у ТС. Можно и без него, смотря как реализовывать.

Добавлено через 41 минуту
Вот вычисление с помощью рекурсии (но сомневаюсь, что код оптимальный):
C++
1
2
3
4
5
bool fun ( int num, int del=2){
    if(del > num/2)
        return true;
    return num%del ? fun(num,++del) : false;
}
Вот тест Миллера-Рабина (являющийся изначально вероятностным), который в данном случае определяет число до 341 550 071 728 321 с полной определенностью (скорость работы не проверял, но должна быть вроде неплохой): http://rosettacode.org/wiki/Mi... C728.2C321
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// calcul a^n%mod
size_t power(size_t a, size_t n, size_t mod)
{
    size_t power = a;
    size_t result = 1;
 
    while (n)
    {
        if (n & 1)
            result = (result * power) % mod;
        power = (power * power) % mod;
        n >>= 1;
    }
    return result;
}
 
// n−1 = 2^s * d with d odd by factoring powers of 2 from n−1
bool witness(size_t n, size_t s, size_t d, size_t a)
{
    size_t x = power(a, d, n);
    size_t y;
 
    while (s) {
        y = (x * x) % n;
        if (y == 1 && x != 1 && x != n-1)
            return false;
        x = y;
        --s;
    }
    if (y != 1)
        return false;
    return true;
}
 
/*
 * if n < 1,373,653, it is enough to test a = 2 and 3;
 * if n < 9,080,191, it is enough to test a = 31 and 73;
 * if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
 * if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;
 * if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;
 * if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;
 * if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.
 */
 
bool is_prime_mr(size_t n)
{
    if (((!(n & 1)) && n != 2 ) || (n < 2) || (n % 3 == 0 && n != 3))
        return false;
    if (n <= 3)
        return true;
 
    size_t d = n / 2;
    size_t s = 1;
    while (!(d & 1)) {
        d /= 2;
        ++s;
    }
 
    if (n < 1373653)
        return witness(n, s, d, 2) && witness(n, s, d, 3);
    if (n < 9080191)
        return witness(n, s, d, 31) && witness(n, s, d, 73);
    if (n < 4759123141)
        return witness(n, s, d, 2) && witness(n, s, d, 7) && witness(n, s, d, 61);
    if (n < 1122004669633)
        return witness(n, s, d, 2) && witness(n, s, d, 13) && witness(n, s, d, 23) && witness(n, s, d, 1662803);
    if (n < 2152302898747)
        return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11);
    if (n < 3474749660383)
        return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13);
    return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13) && witness(n, s, d, 17);
}
Добавлено через 41 минуту
size_t лучше заменить на unsigned __int64 или unsigned long long, а в конце (больших) чисел дописывать ui64 или ull.
Код проверил, работает быстро, но, например, числа 68718952447 и 63018038201 не считает простыми (1073676287 определяет верно как простое). Возможно, нужна еще длинная арифметика, но упоминаний об этом не видел.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.04.2015, 19:16
Помогаю со студенческими работами здесь

Проверка числа на простоту
Помогите решить 2 задачки, пожалуйста, 1. Написать программу для проверки натурального числа N...

Проверка числа на простоту
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители...

Проверка числа на простоту
Хочу проверить число на простоту, но не вижу ошибку в коде. Можете подсказать, что не так? ...

Проверка числа на простоту
Дано натуральное число n&gt;1. Проверьте, является ли оно простым. Программа должна вывести слово YES,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru