carmichael

Une méthode rapide de vérifier qu’un nombre est premier est d’utiliser le petit théorème de Fermat

Théorème 1. Si p est un nombre premier et a premier avec p alors ap−1 ≡ 1 (mod p)

La réciproque est fausse. Les nombres ne vérifiant pas la réciproque sont les nombres de Carmichael et il y en a peu. On regarde le nombre de nombre pseudo-premier pour un entier de référence a fixé. Pour chaque triplet a < 10^4 , n1 < 10^6 , n2 < 10^6 et n1 ≤ n2 vous devez renvoyer le nombre de nombres entre n1 et n2 (au sens large) qui vérifient les hypothèses de la réciproque du petit théorème de Fermat pour a (i.e. a premier avec p et a p−1 ≡ 1 (mod p)) mais qui ne sont pas premier.

Input

9 32 64
4 7 31
2 29 59
3 7 17
11 82 84
5 60 66
3 12 58
2 71 77
2 17 48
10 8 33
7 59 93
6 20 82
6 16 60
2 51 69
4 19 59
3 8 98
5 19 45
7 2 93
5 70 93
7 73 85

Télécharger l'entrée

Output

1
1
0
0
0
0
0
0
0
2
0
1
1
0
0
1
0
2
0
0

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.