Back
Close
  • 162

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

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

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