1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool isPrime(unsigned long num, unsigned long *divisible) {
// The formula 6n +- 1, explained in the comment below, only finds primes above 3
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0) {
*divisible = 2;
return false;
}
if (num % 3 == 0) {
*divisible = 3;
return false;
}
// All prime numbers follow the formula 6n +- 1 (where n >= 1). All composite numbers are made up of prime numbers, so this way, we skip iterating through a lot of nums.
// The biggest number we need to check is the square root of num. Otherwise, we're gonna have situations like 5 * 20 and 20 * 5.
// Source (didn't look at example code): https://en.wikipedia.org/wiki/Primality_test#Simple_methods
// It must be n - 1 <= max, and not n + 1 <= max, because there are some cases, where n + 1 > sqrt(num) but n - 1 == sqrt(num)
// For example: 289, 323, 2209, 10201, 22201
for (unsigned long n = 6, max = sqrt(num); n - 1 <= max; n += 6) {
if (num % (n - 1) == 0) {
*divisible = n - 1;
return false;
}
if (num % (n + 1) == 0) {
*divisible = n + 1;
return false;
}
}
return true;
}
int main() {
char numberInput[20];
printf("Natural number, up to 2^64-1: ");
fgets(numberInput, 20, stdin);
unsigned long number = 0, divisible = -1;
sscanf(numberInput, "%lu", &number);
if (isPrime(number, &divisible))
printf("Your number is prime!");
else
printf("Your number is not prime! It is divisible by %ld!\n", divisible);
}
|
