All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Coprimes
/

Ad-Hoc, Algorithms, Coprime, Greedy Algorithms

Problem
Editorial
Analytics

You are provided an integer \(n\). Your task is to determine the largest integer \(a\) (\(a<n-1\)) 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 \leq n \leq 10^{3}\)

SAMPLE INPUT
4
SAMPLE OUTPUT
1
Explanation

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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?