Well, let's say the program will work with primes up to 100,000. We write a program that gives a string like:

int prostie[] = {2,3,5,7,11,13 ...}

Paste into the main program (which we will ask as a solution). We add the code. Shakes Run... Code is too long... Google, it turns out there is a limit of 64 KB. In normal programs, such data is displayed in a separate file. But in olympiads, as a rule, only one file can be submitted - the code itself. Bummer. What to do?

  • 2
    Obviously; search for such an algorithm so that the source code and supporting information are placed in 64K. Then this same information can be shoved into the source. - VladD
  • one
    Try ziping them up with a comma for example. The result of the compression is inserted in a line into the code, and then unpacked. If all the same is not enough, then you can save on commas — write down all the prime numbers on a single line without separators, but first remembering from which positions the two-digit, three-digit, four-digit, etc. prime numbers begin. ---------- In my case, for example, all primes up to 100k separated by a comma after compression took 23 kb. - ReinRaus 5:56 pm
  • one
    Regular zip :) But any hemorrhoids, agree, you can pack more efficiently, but to write a program for this, it seems to me too much. You can just write an Erastophen sieve in a half-kilobyte, and assume that this is an archiver of prime numbers :) - ReinRaus
  • 2
    My option is that there is a sense to store only numbers like 6n+1 and 6n+5 for n> 0. Simple ones up to 6 are understandable. All numbers of a different type greater than 6 will be guaranteed to be composite (this is easily proved at the level of the third class). This reduces the number of numbers already 3 times. Further, these numbers can be stored for 1 bit per number. As a result, one byte "holds" 24 numbers. - KoVadim
  • one
    I packed it in 1K :-) Windows 7 is required for unpacking. --- @ReinRaus: a really good packer should use Eratosthenes to prime numbers. Or something more abruptly. (If you look at the definition of the complexity of information on Kolmogorov as the length of the shortest program that gives this information.) - VladD

1 answer 1

You can store prime numbers through a bitmask. It is very effective and it is in memory limit.

I will give the code on Scala, because there already is a ready-made BitSet data structure:

 // Простые числа до 500 (для 100000 аналогично, только массив побольше будет) val bitMask = Array(2891462833508853932L, -9222764410617429368L, -9212077268751349240L, 577166812715155618L, 2488238931731062914L, -8637762788791285760L, 613193408596549664L, 2261147810570754L) BitSet.fromBitMask(bitMask).foreach(println)

Those. it is necessary to prepare a bit mask in advance “offline” via the BitSet.toBitMask method. A BitSet of prime numbers can be filled in any convenient way, at least a complete search.

  • one
    @orionll, are you serious? - How much space will a bit mask take for 32-bit prime numbers? Consider that 512Mbytes is not enough? Yes, for 100,000 it will take 25,000 bytes, but still not very impressive compression. - avp
  • 2
    Well, in the formulation of the problem, it is said that 100000. It would be said that 2 ^ 32 would be a different conversation. - ZhekaKozlov