0

First of all, I am fairly new to C, and know nothing about C++, and only took the w3schools.org tutorial on C, and made a few practice programs. What I am looking for is something simple that can find all primes form 1 to 1000000 in under half an hour. I do not know how to implement anything complex like Sieve of Atkin or other complex algorithms. Can you either explain Sieve of Atkin either simpler (like in laymen's terms) or demonstrate it in C? Please keep in mind that I just took the beginner course in C from w3schools.

The code that I am using is as follows:

#include <stdio.h>

int n = 0, i, b, e, flag = 0;

int main() {
    printf("Enter a positive integer that will be the higher bound: ");
    scanf("%d", &b);

    for (n = 0; n < b; n++) {
        if (n == 0 || n == 1) {
        flag = 1;
        }
      for (i = 2; i <= n / 2; ++i) {
        if (n % i == 0) {
          flag = 1;
        }
      }
      if (flag == 0) {
        printf("%d is a prime number.\n", n);
        } else {
        }
        flag = 0;
    }
  return 0;
}
inyourface3445
  • 173
  • 10
  • 1
    _"1 to 1000000 in under half an hour"_: half an hour for this is incredibly slow. I think even the dumbest algorithm should be faster than that on an average desktop PC. – Jabberwocky Feb 28 '22 at 16:31
  • 3
    BTW: google "sieve of eratosthenes". This is quite efficient and really simple. – Jabberwocky Feb 28 '22 at 16:32
  • The baseline test that I used is on the basic plan on the online IDE replit.com. I forget the exact specs, but they are not good. I will run it on my home computer and update it accordingly. EDIT: It works by dividing n by every number less then n, if all of them are not devisable, then it is a prime. – inyourface3445 Feb 28 '22 at 16:32
  • Even the dumbest algorithm would be able to find the first 1000000 prime numbers on a platform with very little performance in a couple of seconds. – Jabberwocky Feb 28 '22 at 16:36
  • `for (int i = 2; i <= 1000000; i++) { int f = count_factors(i); if (f == 2) printf("%d is prime.\n", i); }`. Writing the function `count_factors()` is left as an exercise :) – pmg Feb 28 '22 at 16:42
  • So what's the problem on repl.it? Maybe you should [edit] and show your code instead of just describing it. – Jabberwocky Feb 28 '22 at 16:43
  • Approximately the crudest function (which mistreats both 0 and 1 as prime numbers) — `static int IsPrime(unsigned number) { for (unsigned i = 2; i < number; i++) { if (number % i == 0) return 0; } return 1; }` — takes under under 2 minutes for the numbers up to one million running on a MacBook Pro using macOS Big SUr 11.6.4 — 2.6 GHz 6-core Intel Core i7. I got times of 1m 16s and 1m 15s. – Jonathan Leffler Feb 28 '22 at 17:04
  • see [Prime numbers by Eratosthenes quicker sequential than concurrently?](https://stackoverflow.com/a/22477240/2521214) for full set of ideas ... `primes form 1 to 1000000 in under half an hour` ??? more like below 40ms with SoE on 10+ year old PC... on what are you computing old 8bit Z80 with 3.5MHz? – Spektre Mar 01 '22 at 09:31

1 Answers1

1

OP's code limits factor testing with for (i = 2; i <= n / 2; ++i) { - a modest first step.

Yet past the square root of n , there are no factors. Since the root is smaller (usually) , than n/2, this is much quicker.

We could use test_factor * test_factor <= n, but test_factor * test_factor may overflow. Use test_factor <= n/test_factor. Smart compilers will see the nearby n/test_factor and n%test_factor and emit code that executes about as fast as just one of those.

Code could calculate int limit = sqrt(n), but that 1) has edge case problems as sqrt() may no return exactly the sought after root even when it is a whole number 2) may lose needed precession when the integer type has more precision that double. 3) Incurs a floating point cost vs. the nearly no additional cost of test_factor <= n/test_factor.

OP's code sets a flag when a factor is found and then continues to look for more. Yet there is no reason to continue looking. This speeds things up a lot to quit the loop once a factor is found.

We could also check every other value as numbers divided by 2 are not prime - with one exception: 2. This is a modest improvement.

bool is_prime(int n) {
  if (n % 2 == 0) {
    return n == 2;
  }
  for (int test_factor = 3; test_factor <= n / test_factor; test_factor += 2) {
    if (n % test_factor == 0) {
      return false;
    }
  }
  return n > 1;  // No factors and n is more than 1.
}

Use

for (n = 2; n < b; n++) {
  if (is_prime(n)) {
    printf("%d is a prime number.\n", n);
  }
}

Note: less than 2 seconds to print all the primes less than 1000000.

For a sieve approach. See Sieve of Eratosthenes pseudo code.

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256