#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);
}