Improve prime filtering code - O(n^2) to O(n) and remove redundant elements of array

Question

This code I created iterates through numbers 1-100 and eliminates non-primes i.e leaves 2,3,5,..97. However, it contains 2 for loops for the sorting algorithm and is therefore slow. On top of this, the number "0" remains in the spot of the eliminated number.

My question is, how can I bring this program to O(n) performance and how can I copy the primes in nums[] to another array so that they're in order?

#include <stdio.h>

#define MAX 100

int main ()
{
    int nums[MAX];
    int i,j;

    for (i=0;i<MAX;i++)
    {
        nums[i] = i;  //Place numbers from 1 to 100 in the array
    }

    for (i=0;i<MAX;i++)  //Loops through each number in the array
    {
        for (j=2;j<=9;j++) 
            /* This loop iterates from 2 to 9 and checks if 
            the current number is divisible by it. If it is,
            it replaces it with 0.*/
        {
            if (nums[i] == 1 || nums[i] == 4 || nums[i] == 6 || nums[i] == 8 || nums[i] == 9 || nums[i] == 10 )
            /*Excludes non-primes less than 11*/
            {
                nums[i] = 0;
            }

            if ((nums[i]%j)==0 && nums[i] > 11)
            {

                nums[i] = 0;
            }
        }
    }

    for (i=0;i<MAX;i++)
    {
        printf("%d ", nums[i]);
    }
    return 0;
}

Thanks for your help in advance!

Answer 1

I don't know what you're intend to do. But if its a prime generator then look at this condition in your code if ((nums[i]%j)==0 && nums[i] > 11)nums[i] = 0 . You're filtering the non-primes here if I'm not wrong.Yea it'll filter bellow 100 correctly.But what about a number multiple of 11 or 13 lets say 121 or 169 these will not filter down being non-prime. Then you've to add more numbers in your checker. So its not a good filter at all.
Lets design a filter :) , you know all primes are odd number except 2.

So first of all we'll filter all even number from our list.Lets say we have an array of 0's and after we filter which index will remain 0 are primes.

for(int a=4; a<MAX; a+=2)nums[a]=1;
//remove all even(multiple of 2) number, except 2 

now we'll filter the odds which are multiple of ther odd's like 9,15,121 etc. Lets start from first odd num and filter all their multiples

for(int a=3; a<MAX; a+=2) //all odd num below MAX
{
    for(int b=a*2; b<MAX; b+=a)nums[b]=1;
    //multiple of a's are a*2,a*2+a,a*2+a+a .... 
}

So in this loop when we are getting a odd num we're filtering all its multiple. So all the odd nums which haven't filtered down are prime cause they have no divisor except 1 and itself.

Now to check the result loop through the nums array which index are still 0

for(int a=2;a<MAX; a++)if(!nums[a])printf("%d ", a);

Yeah you get the idea I think and this approach called sieve of Eratosthenes .

And you can optimize what I've done a bit if you want.

Answer 2

Yes there are O(N) prime generators out there (where N is number of primes not the range size for those this runs in sub-linear time). For example Euler's formula (from Project Euler 27):

p = n² + n + 41;  n={0,1,2,...39}

Here comparison of formula output against primes:

Output: 41,43,47,53,...61,...71,......83,...97,................113,....131,............151,............173,................197,........223,....................251,....................281,................313,............347,........................383,....................421,........................461,........................503,................547,........................593,............................641,................................691,........................743,........................797,............................853,................................911,............................971,.........................................1033,.............................................1097,...................................1163,...................................1231,.......................................................1301,...................................1373,........................................1447,.......................................................1523,..................................................1601
Primes: 41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601

As you can see it produced primes in order but not all of them. Such generators are limited to specific ranges. There are also numeric approaches to generate such formulas on specific ranges but to obtain them is much much harder than O(N).

What you need is to make an approximation polynomial that would work on <1,100> but that would need probably high degree polynomial to maintain precision (or use it piece wise). So google polynomial fitting But better option would be PSLQ.

For more ideas about how to improve your sieve prime generator Take a look at:

• Prime numbers by Eratosthenes quicker sequential than concurrently?