Oros Ioana Diana at 14:00, 18 May 2024

2024-05-18T14:00:44Z

Oros Ioana Diana: Pagină nouă: == 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ă...

2024-01-08T20:49:55Z

Pagină nouă: == 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ă...

New page

== 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 ==
<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:
 
'''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.

3897 - Josephus Sequence - Revision history

Oros Ioana Diana at 14:00, 18 May 2024