UVA 10042 (Smith Number)
10 views
Skip to first unread message
Atiqur Rahman
Dec 25, 2008, 11:24:13 AM12/25/08
to Online Judge Helps
It's AC. It's one of the easy problems related to Number theory
(Prime)
A theory has helped me much "A number if divided by all its prime
factor upto square root of that number result is one or a prime
number"
As the input range is upto 10^9 I only pre-calculated 40,000 prime
numbers which are required upto the square root.. And that worked
fine.
Some input/outputs in case anyone fails to get AC.
Input
=======
7
1
5
22
31
4937774
4937775
999999999
31601
Output
=======
4
22
27
58
4937775
4937818
1000000165
31639
(Prime)
A theory has helped me much "A number if divided by all its prime
factor upto square root of that number result is one or a prime
number"
As the input range is upto 10^9 I only pre-calculated 40,000 prime
numbers which are required upto the square root.. And that worked
fine.
Some input/outputs in case anyone fails to get AC.
Input
=======
7
1
5
22
31
4937774
4937775
999999999
31601
Output
=======
4
22
27
58
4937775
4937818
1000000165
31639
Reply all
Reply to author
Forward
0 new messages