Back
Close
  • 124

What will I learn?

Arithmetics

Statement

 Goal

You might know Fermat’s small theorem:
If n is prime, then for any integer a, we have a^na mod n, that means that a^n and a have the same remainder in the euclidian division by n.

There are numbers, called Carmichael numbers, that are not prime but for which the equality remains true for any integer a.
For example, 561 is a Carmichael numbers because for any integer a, a^561a mod 561. It’s in fact the smallest Carmichael number.

You have to tell if the given number is a Carmichael number or not. Beware, you might be given a prime number.
Input
A single number n.
Output
YES if n is a Carmichael number, or NO if it’s not.
Constraints
1⩽n⩽1000000
Example
Input
12
Output
NO
Solve it

A higher resolution is required to access the IDE

codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants