Блог пользователя tumaryuido

Автор tumaryuido, история, 6 лет назад, По-английски

Recently i got a task from my teacher: Given two numbers n and m(10^10<=n<=10^11. 1<=m<=10^5) Find all prime numbers in range [n, n + m].

1 sec, 32 mb

Help plz

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Use segmented sieve, here's a nice tutorial on it: https://forthright48.com/2015/09/segmented-sieve-of-eratosthenes.html

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

Note that if an integer x in the range [n, n + m] is non-prime, than it should be divisible by some prime number p ≤ P, where , N = 1011 and M = 105. Hence, the required numbers may be found by excluding all non-prime numbers in this range. The performance of the solution may be improved by observing that all the required numbers are odd numbers. A non-prime odd number is the product of two odd numbers.