Prime Filter — Beginner Project Looking for Feedback
I’ve been learning programming recently, and one day while watching a YouTube video I remembered the rule that a number is divisible by 3 if the sum of its digits is divisible by 3.
That made me curious about whether simple mathematical rules like this could help reduce the amount of work needed when checking for prime numbers.
So I started experimenting with prime number optimization problems as a way to improve my understanding of:
-
algorithms
-
filtering
-
performance
-
computational efficiency
This project is called Prime Filter.
The basic idea is simple:
before running a more expensive prime check, I try to eliminate numbers early using lightweight filters such as:
-
even number checks
-
last digit filtering
-
digit sum rules
After filtering, the remaining numbers go through a standard prime-checking function.
I know this is probably not the best or most advanced approach, but the goal of this project is learning and experimentation rather than building a perfect solution.
I also want to be transparent that I built a large part of this project with the help of AI tools. I used AI to:
-
understand concepts
-
explore optimization ideas
-
structure experiments
-
improve and rewrite parts of the code
Even with AI assistance, I still spent time trying to understand the logic and experimenting with different approaches myself.
I used C for this project because it was the only language besides Python that I could realistically work with, and I wanted more accurate performance measurements than I expected from Python.
That said, I’m still very much a beginner in C and generally more comfortable with Python. If there are ways to do this kind of experimentation properly in Python while still getting reliable benchmarking results, I’d really appreciate suggestions.
Here is the current version of the experiment:
#include <stdio.h>
#include <math.h>
#include <time.h>
typedef int (*filter_fn)(int);
/* ---------------- PRIME SOLVER ---------------- */
int base_prime(int n) {
if (n < 2) return 0;
int limit = (int)sqrt(n);
for (int i = 2; i <= limit; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
/* ---------------- DIGIT UTIL ---------------- */
int digit_sum(int n) {
int s = 0;
while (n > 0) {
s += n % 10;
n /= 10;
}
return s;
}
/* ---------------- FILTERS ---------------- */
int filter_even(int n) {
if (n == 2) return 1;
return n % 2 != 0;
}
int filter_last_digit(int n) {
if (n < 10) return 1;
int last = n % 10;
if (last == 0 || last == 2 || last == 4 || last == 5 || last == 6 || last == 8)
return 0;
return 1;
}
int filter_digit_sum(int n) {
if (n <= 3) return 1;
return digit_sum(n) % 3 != 0;
}
/* ---------------- EXPERIMENT RUNNER ---------------- */
void run_experiment(const char *name, filter_fn filters[], int filter_count, int limit) {
int filtered = 0;
int tested = 0;
int primes = 0;
clock_t start = clock();
for (int n = 2; n < limit; n++) {
int skip = 0;
for (int i = 0; i < filter_count; i++) {
if (!filters[i](n)) {
filtered++;
skip = 1;
break;
}
}
if (skip) continue;
tested++;
if (base_prime(n))
primes++;
}
clock_t end = clock();
double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("\n=== %s ===\n", name);
printf("filtered: %d\n", filtered);
printf("tested: %d\n", tested);
printf("primes: %d\n", primes);
printf("time: %f sec\n", time_spent);
}
/* ---------------- MAIN ---------------- */
int main() {
int limit = 10000000;
/* experiment setups */
filter_fn none[] = {};
filter_fn even_only[] = {
filter_even
};
filter_fn last_digit_only[] = {
filter_last_digit
};
filter_fn digit_sum_only[] = {
filter_digit_sum
};
filter_fn combined[] = {
filter_last_digit,
filter_digit_sum
};
run_experiment("baseline", none, 0, limit);
run_experiment("even filter", even_only, 1, limit);
run_experiment("last digit filter", last_digit_only, 1, limit);
run_experiment("digit sum filter", digit_sum_only, 1, limit);
run_experiment("combined filters", combined, 2, limit);
return 0;
}
At the moment, I’m mainly looking for feedback from more experienced programmers.
I would especially appreciate feedback on:
-
whether these filters actually help performance
-
mistakes in my logic or assumptions
-
bad coding practices I should fix early
-
cleaner ways to structure this experiment
-
better mathematical or algorithmic approaches
-
what concepts I should study next
Since I’m still a beginner, even simple explanations or criticism would help a lot.
The main purpose of this project is to learn how to think about optimization, filtering, and computational efficiency in real programs.
while i was trying this i found that gpu are good at parallel work but only at simple mathematical work only and i thought that this filter could simplify the process such that it can run in batches in parallel . but as it is i do not understand enough of programing in general and gpu to implement this and see the improvement . i also do not have gpu to test on so this is mostly theoretical .