Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 30.07.2008, 17:57
Побережный Александр

 
Сообщений: n/a

Ближайшее простое.
Уважаемые софорумники!
Путем несложных расчетов пришел к любопытному результату.
На отрезке [N;N+(lnN)^2] начиная с N=12 всегда будет находиться не менее двух простых чисел.
На небольших числах проверял, все работает.
Хотелось бы узнать мнение авторитетных товарищей в этой области.
  #2  
Старый 30.07.2008, 18:40
Аватар для Schemer
Пользователь

Отправить личное сообщение для Schemer Посмотреть профиль Найти все сообщения от Schemer
 
Регистрация: 26.07.2008
Адрес: Moscow
Сообщений: 93

По теореме о простых чисел (Prime number theorem), число простых чисел меньше N равно примерно (а точнее - при стремлении N к бесконечности) N/log(N), т.е. вероятность что некоторое случайное число x рядом с N простое примерно 1/log(N).
Ну а значит разумно предположить, что для того чтобы найти простое число следующее за некоторым числом N, в среднем потребуется перебрать около log(N) чисел.
  #3  
Старый 30.07.2008, 18:55
Побережный Александр

 
Сообщений: n/a

Уточнение
Простые числа распределены очень неравномерно. Поэтому ваша оценка очень приблизительная. Бывают весьма большие отрезки составных чисел. В моем утверждении говорится, что вы гарантировано найдете два простых числа на данном отрезке. Для программирования это полезная информация.
  #4  
Старый 30.07.2008, 19:41
Аватар для Schemer
Пользователь

Отправить личное сообщение для Schemer Посмотреть профиль Найти все сообщения от Schemer
 
Регистрация: 26.07.2008
Адрес: Moscow
Сообщений: 93

Цитата:
Простые числа распределены очень неравномерно. Поэтому ваша оценка очень приблизительная.
Разумеется. Но на практике такая эвристическая оценка в log(n) (как _среднего_ расстояния между соседними простыми числами) довольно часто используется.

Вообще, про расстояния между простыми есть неплохая страничка - http://primes.utm.edu/notes/gaps.html
Судя по всему вашу предположение про log(n)^2 там названо как Cramer's conjecture (недоказанное), выдвинутое еще в 1936 году.
  #5  
Старый 30.07.2008, 20:22
Побережный Александр

 
Сообщений: n/a

Дополнение
Да, похоже это по моей теме. Единственное, на что я хотел бы обратить внимание, что в моем утверждении будет существовать два и более простых числа на этом промежутке.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра