Форум программистов, компьютерный форум, киберфорум
Алгебра, теория чисел
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/14: Рейтинг темы: голосов - 14, средняя оценка - 4.64
0 / 0 / 0
Регистрация: 08.01.2012
Сообщений: 37
1

Алгоритм поиска простых чисел.

08.01.2012, 02:17. Просмотров 2840. Ответов 4
Метки нет (Все метки)

Нашел пример алгоритма, используемого для получения всех простых чисел от 2 до заданного путем перебора. В нем для каждого числа (i) проверялось, делится ли оно без остатка на другое число (j, делитель), так же перебирающееся. Причем делитель перебирается от 2 до корня из полученного перебором числа (i) включительно. Вопрос: почему же стоит перебирать только до корня? Желательно с доказательством
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.01.2012, 02:17
Ответы с готовыми решениями:

Алгоритм для нахождения больших простых чисел
Подскажите, пожалуйста, алгоритм для нахождения больших простых чисел.

Алгоритм поиска чисел по заданным параметрам
Наткнулся на задачу, к которой никак не могу подобрать более «изящного» алгоритма чем простой...

Содержится ли множество простых чисел во множестве нечетных чисел
Содержится ли множество простых чисел во множестве нечетных чисел? Я считаю, что нет. Поскольку 2 -...

Ищется алгоритм поиска максимума на изменяемой двумерной поверхности
Ищется алгоритм ну или какие то вводные "куда копать". Дано: некая местность (границы...

4
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
08.01.2012, 16:25 2
если прошли дальше корня то число большее чем sqrt(n) явно не будет делителем, потому ччто перебрали все делители до корня , значит на что его умножать чтобы получить n ?только на число большее чем sqrt(n) что невозможно
1
0 / 0 / 0
Регистрация: 08.01.2012
Сообщений: 37
08.01.2012, 16:54  [ТС] 3
Я правильно понял: сам sqrt(n) делителем простого числа не будет, поэтому мы берем число, большее sqrt(n). Тогда, чтобы получить n нам нужно будет это число, большее sqrt(n) возвести в квадрат. Но тогда мы получим число, большее n => имеет смысл перебирать только до корня (включительно, потому что делителем не простого числа n может быть sqrt(n)).
0
Эксперт C
24534 / 15159 / 3205
Регистрация: 24.12.2010
Сообщений: 32,522
08.01.2012, 21:35 4
Лучший ответ Сообщение было отмечено как решение

Решение

Пусть X = p*q
Если p>sqrt(X) и q>sqrt(X) , то X = p*q > X
Перебирать надо до sqrt(X) включительно

Добавлено через 49 минут
Цитата Сообщение от Eugeniy Посмотреть сообщение
но это не значит что оба должны быть не больше
А я этого и не говорил Смысл в том, что если число имеет делители, то один из них <= sqrt(X). и ежели мы не нашли делителей до корня (включительно), то дальше и искать не стоит
4
3127 / 1320 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
08.01.2012, 22:10 5
Байт, все правильно! Главное вовремя исправится!
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.01.2012, 22:10

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Делимость на произведение простых чисел
Добрый день. Столкнулся со следующей проблемой, необходимо найти 5 наибольших собственных делителя(...

Количество чисел взаимно простых с p*q
Нужно доказать, то есть найти кол-во взаимно простых чисел с p*q, если фи(p)=p-1( функция эйлера...

Алгоритм поиска простых чисел
Доброго времени суток. Помогите пожалуйста с алгоритмом поиска простых чисел в массиве. Искал...

Алгоритм поиска n простых чисел
Помогите, пожалуйста, составить батник, находящий простые числа в заданном интервале.


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.