0
Cytat
W trakcie rozglądania się za nową, ciekawą pracą otrzymałem do rozwiązania dość nietypowe (jak na procesy rekrutacyjne) zadanie. Rozwiązywanie go było dość ciekawe, więc pomyślałem, że się podzielę:
LTP (Left-Truncatable Prime) to liczba pierwsza , która
* nie zawiera cyfry 0
* pozostaje liczbą pierwszą po odcięciu dowolnej ciągłej sekwencji cyfr z lewej strony.
Wprowadzenie:
5167 to LTP, gdyż 5167, 167, 67 i 7 są liczbami pierwszymi; 2179 nie jest LTP, bo co prawda 2179, 179 i 79 są liczbami pierwszymi, ale 9 już nie. W przedziale do 1 000 000 000 znajduje się 2166 LTP.
Napisz program, który:
1. przyjmuje pojedynczą liczbę n (1 ≤ n ≤ 2166) jako parametr CLI
2. oblicza n-tą liczbę LTP
3. wypisuje wartość tej liczby na standardowe wyjście
Na przykład:
1. podanie 10 powinno wypisać 47
2. podanie 100 powinno wypisać 5167
3. podanie 1000 powinno wypisać 8391283
Twoje rozwiązanie powinno mieć na uwadze wydajność (choć nie tylko ten aspekt wymaga uwagi). Twój program powinien być w stanie zwrócić odpowiedź w przeciągu 500ms na standardowym PC.
Oprócz tego oryginalne zadanie sugerowało, że rozwiązanie powinno być jakości "produkcyjnej", a stworzenie go nie powinno zająć więcej niż 1h, ale możemy to sobie darować.
Mnie najbardziej interesuje: jakie, droga braci techniczna, masz pomysły na algorytm, i ile czasu/MB pamięci potrzebują wasze rozwiązania? Zaznaczam, że program ma liczby obliczać, więc rozwiązanie typu "ściągam listę LTP z internetu, zapisuję w pliku, a program to tylko wczytuje" jest niekoszerne (taki był mój pierwszy pomysł
A, usłyszałem też, że nawet programiści z wieloletnim doświadczeniem potrafią mieć problemy z rozwiązaniem tego zadania/zapewnieniem odpowiedniej wydajności.
Źródło
