From dbaf69f0e0ede46cbf5765cb6ca9500fcd7a3ea7 Mon Sep 17 00:00:00 2001
From: Syndamia <kamen.d.mladenov@protonmail.com>
Date: Fri, 12 Nov 2021 09:23:19 +0200
Subject: Divided C and C++ files into seperate folders

---
 C/IsPrime.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 C/README.md |  4 ++++
 2 files changed, 53 insertions(+)
 create mode 100644 C/IsPrime.c
 create mode 100644 C/README.md

(limited to 'C')

diff --git a/C/IsPrime.c b/C/IsPrime.c
new file mode 100644
index 0000000..c7c7630
--- /dev/null
+++ b/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);
+}
diff --git a/C/README.md b/C/README.md
new file mode 100644
index 0000000..08e6cde
--- /dev/null
+++ b/C/README.md
@@ -0,0 +1,4 @@
+Building a file:
+```bash
+gcc -o program.out -lm FILE.c && ./program.out
+```
-- 
cgit v1.2.3