var "last" is modified inside loop. It won't cross sqrt(n) .
Also I wanna know is there a faster algorithm ?
Thanks .
That did the job .
from 1 min 5 secs to 2 secs on my test case .
Also what is common practice to reduce I/O overhead in such problems (with Large amount of IO). I pretty much use scanf printf .
8 years later
6 years later
Can someone tell why my code doesn’t work? For the example test cases the output is
1
18446744073709551609
22
#include <stdio.h>
#include <math.h>
size_t divsum(size_t n);
int main(void)
{
int t;
size_t n;
scanf("%d", &t);
while (t--) {
scanf("%lu", &n);
printf("%lu\n", divsum(n));
}
return 0;
}
size_t divsum(size_t n)
{
size_t sum = 1, exp, original = n;
for (size_t p = 2; p <= ceil(sqrt(original)); p++) {
exp = 0;
if (n % p == 0) {
while (n % p == 0) {
exp++;
n /= p;
}
sum *= (pow(p, exp + 1) - 1) / (p - 1);
}
}
return sum - original;
}