Added a check for number being prime

1 files changed, 49 insertions, 0 deletions

diff --git a/C_C++/IsPrime.c b/C_C++/IsPrime.c
new file mode 100644
index 0000000..c7c7630
--- /dev/null
+++ b/C_C++/IsPrime.c
@@ -0,0 +1,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);
+}