10490 - Mr Azad And His Son
24 Nov 2020 — Tags: number_theory,primes — URL- Testing primality up to the square root does the trick.
Implementation details:
- Make sure you precompute the square root, instead of constantly squaring x. That did all the difference for me (from 3s TLE to 0ms AC).
Time complexity: $O(\sqrt{2^n})$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool is_prime(int n)
{
if (n < 2)
return false;
for (int x = 2, sq = sqrt(n); x <= sq; ++x)
if (n % x == 0)
return false;
return true;
}
int main(void)
{
int n;
while (scanf("%d", &n) == 1 && n)
{
if (not is_prime(n))
printf(
"Given number is NOT prime! NO perfect number is available.\n");
else if (is_prime((1LL << n) - 1))
printf("Perfect: %lld!\n", (1LL << (n - 1)) * ((1LL << n) - 1));
else
printf("Given number is prime. But, NO perfect number is "
"available.\n");
}
return 0;
}