Editing 3897 - Josephus Sequence

== Cerința ==
Josephus este un matematician înrăit.
<br>
Î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.
<br>
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
<br>
== Exemplul 2 ==
; josephusin.txt
: 10 3
; josephusout.txt
: 2 5 11 17 23 29 7 13 19 3
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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()

</syntaxhighlight>

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