Matematické Fórum

Problém je následující:

Je dán interval L a U, kde  1<=L<U<=2 147 483 647

rozdíl mezi L a U nepřesahuje 1 000 000


Musím zjistit 2 prvočísla, které mají nejmenší a 2 prvočísla, které mají od sebe největší vzdálenost v zadaném intervalu <L;U>. V případě že je více takových, tak zjistit první takový pár. Respektive mám napsat program, který to zjistí v co nejkratším čase.

Příklad:
Zadaný interval L = 2, U = 17
Výsledek: prvočísla 2 a 3 jsou v zadaném intervalu nejblíže, prvočísla 7 a 11 jsou nejvzdálenější v zadaném intervalu.

Pro představu například v intervalu od 2 000 000 do 2 500 000 výpočet pomocí Eratosthenova síta trvá kolem 23 sekund. Mám udělat program který pro několik takových zadaných intervalů výpočet zvládne do 3 sekund. Podle mne to chce nějaký jiný nápad, jak výpočet nějak obejít. Za každý nápad, nebo připomínku předem děkuju.


Příklad vzdálenosti všech prvočísel v intervalu 1 000 000 až 1 000 100:
  1000003, 1000033 vzdálenost: 30
  1000033, 1000037 vzdálenost: 4
  1000037, 1000039 vzdálenost: 2
  1000039, 1000081 vzdálenost: 42
  1000081, 1000099 vzdálenost: 18
Výsledek:
prvočísla 1000039, 1000081 jsou nejvzdálenější
prvočísla 1000037, 1000039 jsou nejméně vzdálená


Obrázek algoritmu Eratostheova síta: