Numeri interi tra 1 e 7344 primi con 7344

[irelimax]

Salve a tutti!
Mi sono imbattuto nel seguente esercizio:
Trovare il numero di interi compresi tra 1 e 7344 che sono primi con 7344.
Ho pensato che tale esercizio si basasse sul crivello di eratostene ma con esso trovo soltanto i numeri primi compresi tra 1 e 7344 e non arrivo alla soluzione. QUalcuno sa come potrei procedere? Grazie mille in anticipo!

[perplesso1]

$7344 = 2^4 xx 3^3 xx 17$

devi togliere tutti i numeri pari, poi togli tutti i multipli di $3$, poi togli tutti i multipli di $17$ etc etc ... quelli che ti rimangono sono primi con $7344$, però fai attenzione a non togliere troppa roba...

[Kashaman]

c'è un metodo più veloce. guarda qui, se la conosci, è la risposta al tuo problema.

[poncelet]

Credo che chi ha scritto l'esercizio volesse che si utilizzasse la \(\varphi\) di Eulero come ha giustamente rilevato Kashaman

[irelimax]

si ho risolto! grazie a tutti!