CODEWITHSUNDEEP
cprimes
Michael Ebenstein
Michael Ebenstein

Reputation: 135

Why does this prime number algorithm work?

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int anz;
    scanf("%d", &anz);
    time_t start = time(0);
    int *primZ = malloc(anz * sizeof(int));
    primZ[0] = 2;
    int Num = 0;

    for (int i = 1, num = 3; i < anz; num += 2) {
        for (int j = 1; j < i; j++) {
            if (num % primZ[j] == 0) {
                num += 2;
                j = 0;
            }

            //this part
            if (primZ[j] > i / 2)
                break;
        }

        primZ[i] = num;
        i++;
        printf("%d ,",num);
    }

    time_t delta = time(0) - start;
    printf("%d", delta);
    getchar();
    getchar();
    return 0;
}

The code works perfectly fine, the question is why. The part if(primZ[j] > i/2) makes the program 2 - 3 times faster. It was actually meant to be if(primZ[j] > num/3) which makes perfect sense because num can only be an odd number. But it is the number of found prime numbers. It makes no sense to me. Please explain.

Upvotes: 0

Views: 114

Answers (3)

Jakub Wasilewski
Jakub Wasilewski

Reputation: 2976

The reason is that the actual bound is much tighter than num/3 - you could use:

if (primZ[j] > sqrt(num))

The reason for that being that if a prime higher than the square root of num divides num, there must also be a lower prime that does (since the result of such a division must be lower than the square root).

This means that as long as i/2 is higher than sqrt(num), the code will work. What happens is that the number of primes lower than a number grows faster than the square root of that number, meaning that (completely accidentally) i/2 is a safe bound to use.

You can check out how your i value behaves here - they call it pi(x), the number of primes less than x.

Upvotes: 2

skyking
skyking

Reputation: 14359

You check if the prime is composite by checking if it divisible by already found prime numbers. But in doing so you only have to check up to and including the square root of the number because any number larger than that that divides the number will leave a smaller number than the square root of the number.

For example 33 is composite, but you only have to check numbers up to 5 to realize that, you don't need to check it being divisible by 11 because it leaves 3 (33/11=3) which we already checked.

This means that you could improve your algorithm by

    for (int j = 1; j < i; j++) {
        if( primZ[j]*primZ[j] > num )
             break;

        if (num % primZ[j] == 0) {
            num += 2;
            j = 0;
        }
    }

The reason you can get away with comparing with cutting of at i/2 is due to the distribution of the prime numbers. The prime counting function is approximately i = num/log(num) and then you get that i/2 > sqrt(num).

Upvotes: 4

hassan arafat
hassan arafat

Reputation: 667

It makes sense, since if n has two factors one of them is surely less than or equal to n/2, sense the program found no factors of i in primZ that are less than or equal to i/2 it means there's no factors of i -except 1 of course-.

Sense primZ is sorted in ascending order and j only increases, when primeZ[j] > i/2 it indicates that there's no factors of i in primZ that are less than i/2.

P.S.The point of starting the search is stated in the first part of the for statement num=3 , and the recurring statement num += 2 ensures you only test odd numbers

Upvotes: 0

Related Questions