Safe Password Check
Time limit2sMemory limit256 MB
Given a number P equal to the product of two primes and a threshold K, decide if both primes are at least K, otherwise output the smaller prime.
- Level
Easy3 of 10
- Topics
- Number theory, Math, Brute force
- Solved
- No attempts yet
Problem
A password P is made by multiplying two prime numbers p and q. The password is considered secure only when both prime factors are at least K.
Given P and K, determine whether the password is good. If one of the two prime factors is smaller than K, the password is bad.
Input
The first line contains the password P and the integer K, separated by a space.
P is a decimal integer satisfying 4 <= P <= 10^100, and K satisfies 2 <= K <= 10^6. The password P is the product of two prime numbers.
Output
If the password is good, print GOOD on the first line.
If it is bad, print BAD r, separated by a space. Here, r is the smaller of the two prime numbers that form the password.