Заблокирован
|
||||||
1 | ||||||
Проверка числа на простоту19.04.2015, 10:28. Показов 4184. Ответов 7
Метки нет (Все метки)
я реализовал вот так, но алгоритм очень долгий, мне надо проверять очень большое количество чисел (десятки тысяч) и он так надолго виснет что я так и не смог дождаться конца проверки, может можно сделать как то попроще его?
0
|
19.04.2015, 10:28 | |
Ответы с готовыми решениями:
7
Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка на простоту числа |
7784 / 6553 / 2982
Регистрация: 14.04.2014
Сообщений: 28,615
|
|
19.04.2015, 10:37 | 2 |
Ты весь диапазон long long используешь? Может проще взять готовый список простых чисел и в нём искать?
0
|
Заблокирован
|
|
19.04.2015, 10:44 [ТС] | 3 |
да
а какая разница то? все равно получится точно такой же цикл с тем же числом проходов... я имею ввиду может можно кардинально по другому как то искать? ну там какие то условия проставить... чтобы не было таких здоровых циклов, ибо циклы - это время...
0
|
7784 / 6553 / 2982
Регистрация: 14.04.2014
Сообщений: 28,615
|
|
19.04.2015, 10:50 | 4 |
Поиск в упорядоченном массиве не может быть таким же сложным как деление числа на все меньшие.
Ну если весь диапазон, то, наверное, только так, как у тебя.
0
|
случайный прохожий
2919 / 1936 / 606
Регистрация: 20.07.2013
Сообщений: 5,132
|
|
19.04.2015, 10:52 | 5 |
Проверять можно не до value, а до квадратного корня этой величины.
Тогда, если count будет >= 2, то число не простое. Цикл можно начинать с 2 (тогда условие для count станет другим: >= 1, я прав?). Начиная со значения i = 3 инкрементировать счетчик сразу на 2. После проверки на делимость на 5 не рассматривать делители, кратные 5 (т. е. оканчивающиеся на 0 и 5). И т. д. и т. п. Вроде примерно так. Если ошибаюсь, поправьте. Информацию из памяти взял (а она иногда дает сбои). P.S.: можешь еще здесь Быстрая проверка натурального числа на простоту посмотреть.
0
|
7784 / 6553 / 2982
Регистрация: 14.04.2014
Сообщений: 28,615
|
|
19.04.2015, 11:02 | 7 |
0
|
случайный прохожий
2919 / 1936 / 606
Регистрация: 20.07.2013
Сообщений: 5,132
|
|||||||||||
19.04.2015, 19:16 | 8 | ||||||||||
Нет, до корня, причем, возможно, даже не включая его.
count у ТС. Можно и без него, смотря как реализовывать. Добавлено через 41 минуту Вот вычисление с помощью рекурсии (но сомневаюсь, что код оптимальный):
size_t лучше заменить на unsigned __int64 или unsigned long long, а в конце (больших) чисел дописывать ui64 или ull. Код проверил, работает быстро, но, например, числа 68718952447 и 63018038201 не считает простыми (1073676287 определяет верно как простое). Возможно, нужна еще длинная арифметика, но упоминаний об этом не видел.
0
|
19.04.2015, 19:16 | |
19.04.2015, 19:16 | |
Помогаю со студенческими работами здесь
8
Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Проверка числа на простоту Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |