You are running into overflow if this is pseudo-code or
If C code, use of ^
as power operator is not valid.
Working with large integers quickly becomes a problem in C. The are various BigInt
libraries available.
Using floating point is challenging with large integer computation. Recommend avoiding double
, pow()
, etc.
Since the problem is all >= 0, suggest using unsigned integers. Also use the largest integer type available - typically unsigned long long
. As overflow is a real possibility, detect it.
unsigned long long upower(unsigned i, unsigned N) {
unsigned long long power = 1;
if (i <= 1) return i;
while (N-- > 0) {
unsigned long long power_before = power;
power *= i;
if (power < power_before) {
printf("Overflow\n");
return 0;
}
}
return power;
}
void prime() {
unsigned i, N;
scanf("%u", &N);
for (i = 2; i < N; i++) {
if ((upower(i, N - 1) % N) != 1) {
printf("not prime");
return;
}
}
printf("prime");
return;
}
In lieu of huge integers, the Chinese remainder theorem may offer an alternative to (upower(i, N - 1) % N) != 1
.