Optimizing an algorithm to calculate max prime div

Question

this algorithm calculates max prime div using sieve of Eratosthenes. it takes over 7kk kilobytes to calculate x over 1000000000 lol.

some advice how can i optimize it? thanks.

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

int main()
{
int x, p, i, q, max, min;
scanf ("%d", &x);
int *a = (int*)malloc((abs(x)+1) * sizeof(int));
for (i=0; i<=abs(x); i++)
    a[i] = i;
a[1]=0;
for (p=2; p<=abs(x); p++){
        for (q=p*2; q<=abs(x); q+=p)
            a[q]=0;
} 
max=0;
if (x>=0){
    for(i=0; i<=abs(x); i++)
        if((a[i]!=0) && (abs(x)%a[i]==0))
            if (a[i]>max)
                max=a[i];
printf("%d", max);
free(a);
}
else{
min=abs(x);
for(i=0; i<=abs(x); i++)
        if((a[i]!=0) && (abs(x)%a[i]==0))
            if (a[i]<min)
                min=a[i];
printf ("%d", -min);
free(a);
}
}

How much is "7kk kilobytes"? Do you mean 7 gigabytes? 7 megabytes? Or just 7 kilobytes? — Some programmer dude, Oct 18 '17 at 06:22
Doesn't really make a big difference, but you could have `x = abs(x);` right after the `scanf` and get rid of all subsequent calls to `abs`. — Jabberwocky, Oct 18 '17 at 06:23
As for possible way to optimize it, there are quite literally several thousands (if not several tens of thousands) of different implementations of the Sieve of Eratosthenes everywhere on the Internet. You should really try to search more. — Some programmer dude, Oct 18 '17 at 06:24
Because `a[n]` in your programm can only have the values `n` or `0`, you don't need to save them. A bit is enough. On a 32-bit implementation you can reduce the needed memory to 1/32. — Holger, Oct 18 '17 at 06:37
If it works, go to codereview. Stack Overflow is more of a site is for **single most correct answer to a problem**. — Antti Haapala -- Слава Україні, Oct 18 '17 at 07:44
[Don't cast the result of `malloc` in C](https://stackoverflow.com/q/605845/995714) — phuclv, Oct 18 '17 at 15:29

score 0 · Answer 1 · answered Oct 18 '17 at 15:20

You can do implementation optimizations (like using one bit instead of 32) but it will at most get you a 32 optimization factor.

A more interesting thing would be to do algorithm optimisation (like not computing the full sieve but only to sqrt(x))

int x, p, i, q;
scanf_s("%d", &x);
x = abs(x);
int size = sqrt(x); // there is at most one prime number that divide x bigger than sqrt(x)
int *a = (int*)malloc((size + 1) * sizeof(int));
for (i = 0; i <= size; i++)
    a[i] = i;
a[1] = 0;
for (p = 2; p <= size; p++) {
    if (a[p] == 0) { // p is not prime you can skip p
    }
    else {
        while (x % p == 0) { // if p div x, divide it as much as possible
            x /= p;
        }
        if (x == 1) {
            printf("%d", p); 
            break;
        }
        for (q = p * p; q <= size; q += p)
            a[q] = 0;
    }
}
if (x != 1)
    printf("%d", x);
    free(a);
return 0;

Optimizing an algorithm to calculate max prime div

1 Answers1