3897 - Josephus Sequence

Cerința

Josephus este un matematician înrăit.
Într-o zi acesta se joacă cu primele N numere prime, când se decide să își construiască propiul său șir circular format din aceste numere. Pe prima poziție se va afla primul număr prim, adică 2, iar mai apoi se parcurge circular șirul din K în K, completându-se cu restul de numere prime, până la repartizarea tuturor.
Din nefericire lui Josephus, i-a venit somnul, așa, că vă roagă pe voi să îi construiți șirul.

Date de intrare

Fișierul de intrare josephusin.txt conține pe prima linie numărul N și numărul K.

Date de ieșire

Fișierul de ieșire josephusout.txt va conține N numere naturale separate prin câte un spaţiu, reprezentând şirul lui Josephus.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000
• 1 ≤ K ≤ 1.000.000.000
• cel de-al 1.000.000 număr prim este 15.485.863

Exemplul 1

josephusin.txt

5 4

josephusout.txt

2 5 11 7 3

Exemplul 2

josephusin.txt

10 3

josephusout.txt

2 5 11 17 23 29 7 13 19 3

Rezolvare

#3897 - Josephus Sequence
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def generate_primes(N):
    primes = []
    num = 2
    while len(primes) < N:
        if is_prime(num):
            primes.append(num)
        num += 1
    return primes

def josephus_sequence(N, K):
    primes = generate_primes(N)
    josephus_list = []
    index = 0

    for _ in range(N):
        index = (index + K - 1) % len(primes)
        josephus_list.append(primes.pop(index))

    return josephus_list

def main():
    try:
        with open("josephusin.txt", "r") as file:
            N, K = map(int, file.readline().split())

        if not (1 <= N <= 1000000 and 1 <= K <= 1000000000):
            print("Fals")
            return

        josephus_result = josephus_sequence(N, K)

        with open("josephusout.txt", "w") as file:
            file.write(" ".join(map(str, josephus_result)))

    except Exception as e:
        print("Fals")
        print(f"Error: {str(e)}")

if __name__ == "__main__":
    main()

 Explicatie 

Distribuirea se face astfel:
2 5 11 7 3 numărând din 4 în 4, începând cu primul termen, se obţine următoarea listă:
2 3 5 7 11 reprezentând primele 5 numere prime.