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

How to find prime numbers in some interval?
Автор onlydmc123, 10 лет назад, По-английски

I know that you can use sieve of Eratosthenes for finding all prime numbers in (1,N) interval, but can you suggest algorithm that can do that for (N,M) interval, when N,M are large, for instance 10^9 and N=500,000,000; M=501,000,000.

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

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

If the difference between N and M is less (about 10^5), then a modified sieve will work.
You need to cancel out all multiples of 2, 3, 5, and so on upto prime just less than or euqal to sqrt(M).

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are you talking about this problem?

→ Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Hi, you could search about segmented sieve, look this problem http://goo.gl/6nlsFP and its respective editorial http://goo.gl/oAjzCT both resources belong to codeforces user lbv, I hope that this has been helpful.

→ Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Find all prime numbers between 1 and sqrt(10^9), and for all numbers between m and n look by sieve, all numbers that divisible for this primes(except this primes) is not prime. Аsymptotic will be O(N(log(log(N)))+(n-m)*mehrunesartem(n-m)). If you want, I can write pseudocode.

→ Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

I solved it in , where K = M - N

If there's no divisor of X, which is not greater than , then, there's no divisor, which is greater than , so X is prime.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain how you do it?


    T <= 10
K <= 10^5
Sqrt(M)<=sqrt(10^9)

    I think it will be TLE.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hmm, then I'm not sure :)

      Actually, I think that was O(TKlogM). Half of all numbers divide by 2, 1/3 divide by 3, etc.

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I know, that in java there is method n.nextProbablePrime(), that find first prime number after n and it's complexity is like O(n^(1/3)), but I don't know, how it works.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can use the Miller-Rabin test, which applies Fermat's Little Theorem to test whether a number is prime. So if we're given n, the number we're testing, we write n - 1 = 2ab, and take some integer k and look at kb, k2b, k4b and so on up to k2ab, all modulo p. If we ever have a residue not equal to  ± 1 that squares to become 1 modulo p, we know n can't be prime. This is because if p were prime and x2 ≡ 1 modulo p, then x ≡  ± 1 modulo p. More details can be found in the second half of this PDF.

If the numbers we are all testing are less than 4.7 billion, it suffices to test k = 2, 7, 61, according to this page. And for each test, we can do exponentiation by squaring to get all the needed powers of k in time. So each primality test can be done time, which should be fast enough for the problem. (They usually call Rabin-Miller a time algorithm, but I'm pretty sure that's only after considering implementing bignum multiplication, which we don't have to do because we can just use long long's for everything).

Also, look at this.

→ Ответить