Nederlandse leereditie
Een priemgetal controleren in C
Test delers tot de vierkantswortel en behandel nul en één correct.
Een priemgetal is een geheel getal groter dan één met precies twee positieve delers. Nul, één en negatieve getallen zijn niet priem. Een samengesteld getal heeft minstens één factor die niet groter is dan zijn vierkantswortel.
Sluit even getallen behalve twee uit en test daarna oneven delers. Bij grote positieve waarden voorkomt divisor <= N / divisor overloop van divisor * divisor. Stop zodra je een exacte deler vindt.
Test 1, 2, een kwadraat zoals 49 en een priemgetal. Proefdeling kost O(sqrt(N)) tijd en O(1) hulpruimte.
Broncode
#include <stdio.h>
#include <stdbool.h>
bool is_prime_optimized(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
// Check factors 6k +/- 1 up to sqrt(n)
for (int i = 5; (long long)i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
int main(void) {
int test_numbers[] = {1, 2, 17, 25, 29, 49, 97, 100};
int total = sizeof(test_numbers) / sizeof(test_numbers[0]);
printf("--- Prime Number Verification ---\n");
for (int i = 0; i < total; i++) {
int val = test_numbers[i];
printf("%3d -> %s\n", val, is_prime_optimized(val) ? "PRIME" : "NOT prime");
}
printf("\nPrimes between 1 and 50:\n");
for (int i = 1; i <= 50; i++) {
if (is_prime_optimized(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}Verwacht resultaat
--- Prime Number Verification --- 1 -> NOT prime 2 -> PRIME 17 -> PRIME 25 -> NOT prime 29 -> PRIME 49 -> NOT prime 97 -> PRIME 100 -> NOT prime Primes between 1 and 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Veelgestelde vragen
Waarom blijven code en sommige resultaten Engels?
C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.