bvd's blog

A hard problem from Vietnam Olympiad in Informatics for 9-grader
By bvd, history, 8 years ago, In English

English version

Find all prime numbers between N and M, with 0 < N < M < 1025.

A further classification said that the time limit is 1 second and M - N < 109.

I'm wondering if there is a solution for this problem.

  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm not sure but I don't think there is a solution to this problem for 3 reasons.
1-) It is obvious that we can't iterate over those M-N numbers. It would be 5 * 108 by itself which would exceed 1 sec. run time limit.
2-) Since the numbers are too large we can't use prime sieves either, at least the ones I know.
3-) Even though we find the prime numbers in 0 sec, I assume we won't be able to print them out in 1 sec since there are probably more than 107 prime numbers between N and M in the worst case.
It would be great if someone can find a solution though.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And the main problem is to find prime numbers between 2 strings because of large numbers

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

maybe BigInteger.nextProbablePrime() in java will work? not sure, though.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But we should use Pascal

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The algorithm behind is Miller-Rabin primality test , so you need to implement it yourself

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Miller Rabin will probably be too slow. By the Prime Number Theorem, primes exist below N, and Miller Rabin runs in or something. Even assuming k=1, this means it will take O(N) where N = 1e9. I think you have to find each prime in constant time somehow.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It is not enough, either.

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, it would definitely speed up the process but unfortunately not enough.
    With that function or the algorithm behind it, we still need to check primality of the returned numbers. That means the time complexity is O(primalitytestcomplexity * 107) in the best case when M - N = 109. I don't think there is a primality test with a time complexity of less than O(log2N)

    → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

http://www.wolframalpha.com/input/?i=prime+numbers+less+than+10^9

There are 50000000+ primes under 10^9 :( simply printing these will be a big challenge.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually the 2nd and 3rd problems in this paper were very easy, so I am quite sure that this problem was having some mistakes, or the actual tests' limits are small enough to brute force. Anyway this is the Vietnamese problems' style nowadays.

→ Reply
»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Maybe use range sieve. It will require about sqrt(M) + (M-N) operations and bits of memory, even with inf memory this will take >> than 1 sec

→ Reply
»
8 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Usually the trick to do well in middle school level competitions in Vietnam is to just ignore the unrealistic constraints.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, please explain to me why this problem it's too big limits?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      koosaga has already said: There are 50000000+ primes under 10^9 :( simply printing these will be a big challenge.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • How this problem can be resolved?
        • As always, Maybe a big limit is a good chance to find good student?
        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          This problem is (probably) impossible to be resolve.

          As you can see, I wrote a program 24418001 to print integer from 1 to 50000000 here and submit to a random problem and got TLE(more than 2 second while the time limit here is 1 second).

          I agree that big limit is a good chance to find good student, but giving task that is practically impossible is not the same.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            • Exactly, I agree with your point of view too...
            • But with my opinion, such as age, Such a request is too much...
            → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Long long time ago, the limit of problems wasn't big as present... but nowadays the limit is bigger, bigger after each year. But I think that a 9-grade student doesn't think about Miller-Rabin or some complex algorithms. Maybe a big limit is a good chance to find good student?

      → Reply
»
7 years ago, # |
  Vote: I like it -29 Vote: I do not like it

this problem is not hard , just u r stupid

→ Reply