Coprimes
Practice
3.8 (41 votes)
Ad Hoc
Algorithms
Coprime
Easy
Greedy algorithms
Problem
71% Success 8361 Attempts 10 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are provided an integer n. Your task is to determine the largest integer a (\(a) that is a coprime of n. This implies that gcd(a,n)=1.

Input format

A single line that contains an integer n

Output format

Print the answer to the question.

Constraints

3≤n≤103

Sample Input
4
Sample Output
1
Explanation

Largest integer less than 3 (n-1), coprime with 4 is 1

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Submissions
Please login to view your submissions
Similar Problems
1.Sum of cards
Points:10
9 votes
Tags:
AlgorithmsBasics of Greedy AlgorithmsC++Greedy Algorithms
2.Signaling
Points:10
14 votes
Tags:
Basics of Greedy AlgorithmsGreedy AlgorithmsAlgorithms
3.( Problem A ) Pikachu and the Game of Strings
Points:10
60 votes
Tags:
AlgorithmsEasyGreedy Algorithms
Editorial

Login to unlock the editorial