Witam,
Mam następujący problem, jak sprawdzić mając jakis zbiór cyfr dajmy na to 1,5,8,3 ile liczb pierwszych można z nich stworzyć z tym, że budując liczbę każdą z cyfr możemy wziąć tylko raz...z góry dziękuję za pomoc
0
0
Robisz sito Erastotenesa do liczby 8531 czyli cyfry posortowane nierosnąco.
potem składasz wszystkie możliwe kombinacje:
zaczynasz od 1357
w C++ jest do tego next_permutation, można podejrzeć jak jest zrobione i przerobić na własny kod dostajesz kolejne kombinacje.
oprócz tego (najlepiej rekurencyjnie) powtarzasz to samo ale bez każdej z cyfr (tyle razy ile jest cyfr).
0
Robisz sito Erastotenesa do liczby 8531 czyli cyfry posortowane nierosnąco.
A nie łatwiej jest po prostu rekurencyjnie zbudować listę liczb i od razu sprawdzać czy są pierwsze? Wydaje mi się że budowanie dużego sita Eratostenesa jest bezcelowe.
0
-321oho napisał(a):
A nie łatwiej jest po prostu rekurencyjnie zbudować listę liczb i od razu sprawdzać czy są pierwsze? Wydaje mi się że budowanie dużego sita Eratostenesa jest bezcelowe.
Z całą pewnością nie. Dla zaledwie 4-ch cyfr ilość liczb pierwszych do sprawdzenia wynosi 432=24 a nawet jeżeli to będą cyfry 4321 to dla sprawdzenia czy jest pierwsza trzeba wykonać co najmniej 63 operacji dzielenia, a to jest tylko jedna z 24 liczb.
Z drugiej strony można budując sito od razu sprawdzać czy znalezioną liczbę pierwszą da się przedstawić podanymi cyframi. Ale to i tak będzie wolniej niż poprzednia propozycja.