Форум программистов, компьютерный форум, киберфорум
Наши страницы
Баженов
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Простые числа. Итоги 2018 года.

Запись от Баженов размещена 04.01.2019 в 20:38

О простых числах.
Считаю, что общей теории для проверки простых чисел
построить невозможно ввиду их бесконечного числа.
Можно конечно, придумать уравнение или систему уравнений, но количество переменных всегда будет больше количества уравнений.
Самый простые примеры:
одно jуравнение с двумя переменными N=X*Y
или система трех уравнений X-Y=C, X+Y=D C*D=N с четырьмя неизвестными.
Таким образом,,вопрос сводится только к совершенствованию и оптимизации технических приемов.
Об одном из таких технических приемов и расскажу далее.
Решению вопроса поможет то обстоятельство, что каждое проверяемое число имеет начало и конец (нижнее и верхнее граничные условия).
Для нечетных чисел окончаниями являются числа 1,3,5,7,9. Числа с окончанием на 5 рассматриваться не будут, так как среди них нет простых чисел.
Окончание числа определяет возможные связанные пары
сомножителей.
Например числа с окончанием на 1 имеет только три такие возможные пары:
(10X+1)*(10Y+1)
(10X+3)*(10Y+7)
(10X+9)*(10Y+9).
Вывод: при проверке чисел достаточно использовать только числа одного типа из каждой пары.
Это значительно сокращает число проверок.
Верхнее граничное условие определяет верхнее значение делителя. Он не может быть больше проверяемого числа,
а точнее одной его трети.
Другой прием, связанный с учетом окончания, следующий.
Определим числоj N" = (N- K)/10 (K=1,3,7,9) и введем линейную функцию двух переменных F(X,Y), вид которой будет зависеть от окончания проверяемого числа.
Тогда можно построить равенство (критерий проверки)
N" = 10*X*Y + F(X,Y)
или N" -10*X*Y = F(X,Y) ( 10*X*Y естественно меньше N).
или (N" - F(X,Y))/10 = X*Y (N"-F(X,Y) должно быть больше нуля и кратным 10.
Какой вид критерия проверке предпочтительней?.
Теперь о функции F(X,Y).
Для ее упрощения определим функцию S=X+Y,
Тогда с учетом этого:
для чисел с окончанием 1 получим три вида
F(X,Y)= S
F(X,Y)= 3S+4X+2
F(X,Y)= 9S+8
для чисел с окончанием 3 получим два вида
F(X,Y)= S+2X
F(X,Y)= 7S+2X+6
для чисел с окончанием 7 получим два вида
F(X,Y)= S+6X
F(X,Y)= 3S+6X+2
для чисел с окончанием 9 получим nhb вида
F(X,Y)= S+8X
F(X,Y)= 3S
F(X,Y)= 7S+4.
На одном примере покажу как это работает.
Проверим число 121.
N"=12
(12- S)/10=X*Y
S(1,1)=2 (12-2)10=1=1*1, следовательно X=Y=1 и 121=11*11
или 12-10*1*1=1+1.
Как лучше проверить покажет опыт.
С Новым годом, друзья.!
Размещено в Без категории
Просмотров 167 Комментарии 3
Всего комментариев 3
Комментарии
  1. Старый комментарий
    Продолжу приводить примеры демонстрации этого метода. Для чисел меньше 1000 они у меня есть.
    Запись от Баженов размещена 04.01.2019 в 20:43 Баженов вне форума
  2. Старый комментарий
    Уважаемый Баженов,
    а можно ли написать функцию вычисляющую все простые числа до 1000? Таких простых чисел конечное число (меньше 200). Допустим такая функция (аналитическая) есть, тогда f(1) = 2; f(2) = 3; f(3) = 5; f(4) = 7; f (5) = 11; ... f(10) = 29; ... f(100) = 541; ... и так далее.
    Запись от нтч размещена 05.01.2019 в 10:13 нтч вне форума
  3. Старый комментарий
    Аватар для gunslinger
    В самом начале - решето Эратосфена:
    https://en.wikibooks.org/wiki/Algori...ber_generation
    Запись от gunslinger размещена 05.01.2019 в 19:13 gunslinger вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru