Finding primes from random integers

Question

I was hoping I could get some help making my code more efficient. I'm a math major taking an Intro to Programming class, and I was asked to write a C program that generates:

1. A text file named random_ints.txt containing 1≤n≤1000 random integers, separated by commas, in the range [2,1000000] and;

2. A second file named primes.txt that contains a list of the prime numbers contained in random_ints.txt.

The basic idea of my program is to:

1. Create an array of n random integers and print them onto the first text file.

2. Identify all prime numbers and place them at the beginning of the array.

3. Sort them in non-decreasing order (increasing, with (if any) repetitions)

4. Sort them in strictly increasing order (no repetitions).

5. Print them onto the prime text file.

This is the final revision of my code (which works fine):

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

int prime(int n){                                         /*creates function of primality test*/
    int c = 0; 
    if ( (n <= 0) || (n == 1) )
    {
        return 0;
    }
        else
        {
            for (int k = 2; k <= (int)sqrt((double)n); ++k)
            {
                if( n % k == 0)
                {
                    c = 1;
                }

            }

            if (c == 1)
            {
                return 0;
            }
                else 
                {
                    return 1;
                }
        }
}

int main(void)
{
    int n;

    printf("\nPlease enter a positive amount (less than 1,000) of integers you would like to scan for primality:\n");

    for (;;)
    {
        scanf("%d", &n);

        if (n>=1)
        {
            printf("\n");
            break;
        }

        printf("\nError! Please enter a number between 1 and 1000:\n");
    }


    int random[n];                                        /*begins declaring array*/

    srand(time(0));                                       /*seeds the srand function*/

    for (int i = 0; i < n; ++i)                           /*fills in the array with random numbers from 2 to 1,000,000*/
    {
        random[i] = rand() % (1000000 - 2 + 1) +2;


    FILE *fptr;

    fptr = fopen("random_ints.txt","w");                  /*writes the random numbers of the array onto a text file*/
        for (int i = 0; i < n; ++i)
        {
            if (i == 0)
            {
                fprintf(fptr,"%d",random[i]);
            } 
                else
                {
                    fprintf(fptr,", %d",random[i]);
                }
        }
    fclose(fptr);

    if((n>0) && (n<3))                                    /*deals with case where we have only one or two random numbers, since more than two numbers are needed to work with our for loop in line 119*/
    {
        fptr = fopen("primes.txt","w");                   /*checks whether the numbers are prime and, if so, writes them onto the prime text file*/
            for (int i = 0; i <= n; ++i)
            {
                if (prime(random[i]) == 1)
                {
                    if (i == 0)
                    {
                        fprintf(fptr,"%d",random[i]);
                    } 
                        else
                        {
                            fprintf(fptr,", %d",random[i]);
                        }
                }
            }
        fclose(fptr);
        printf("Success!\n");
        return 0;
    }
        else
        {
            if (n >= 3)                                  /*deals with case where we have 3 or more random numbers*/
            {
                int p1 = 0;                              /*declares variable to be used to keep track of where to place a prime number once it is found on the array*/
                for (int i = 0; i < n; ++i)
                {
                    if (prime(random[i]) == 1)           /*checks every value in the array for primes; if it finds one, saves it on the p1-th place and increases this value by one*/
                    {
                        random[p1] = random[i];
                        p1++;
                    }
                }
                for (int i = p1; i < n; ++i)             /*(now, values from random[0] to random[p1 - 1] will be filled with random prime numbers) sets the rest of values to zero*/
                {
                    random[i] = 0;
                }

                for (int i = 0; i < (p1-1); ++i)         /*organizes the prime numbers in the array from least to greatest*/
                {
                    for (int k = (i + 1); k < p1; ++k)
                    {
                        if (random[i] > random[k])
                        {
                            int temp = random[i];
                            random[i] = random[k];
                            random[k] = temp;
                        }
                    }
                }

                for (int i = 0; i < (p1 - 1); ++i)      /*shifts the array to get rid of repeated primes (except for the last one)*/
                {
                    if (random[i] == random[i + 1])
                    {
                        int m = (i + 1);
                        for (int k = (i + 1); k < p1; ++k)
                        {
                            if(random[i] != random[k])
                            {
                                random[m] = random[k];
                                m++;
                            }
                        }
                    }
                }

                int r = 0; int z = 0;                   /*records where the last non-repeated prime is located*/
                while(random[z] != random[z + 1])
                {
                    r++; z++;
                }

                fptr = fopen("primes.txt","w");
                    for (int i = 0; i < r; ++i)
                    {
                        if (prime(random[i]) == 1)      /*verifies that the numbers on the array are prime then, if so, writes them onto the prime number text file*/
                        {
                            if (i == 0)
                            {
                                fprintf(fptr,"%d",random[i]);
                            } 
                                else
                                {
                                    fprintf(fptr,", %d",random[i]);
                                }
                        }
                    }
                fclose(fptr);
                printf("Success!\n");
                return 0;
            }
                else{
                    return -1;
                }
        }
}

Answer 1

You can simplify a lot your first function, you have a lot of useless statements. Also, you don't have to call sqrt each time, just save the result (I know, optimizer can do it for you but...).

Your code fail if we give 2, it's prime, you don't catch this case. Once you know n is not 2 and nor pair, you can just iterate over odds.

int prime(int n)
{       
    if (n == 2)  return 1;                                   
    if (n <= 2 || !(n % 2))  return 0;
    int n_sqrt = (int)sqrt((double)n);
    for (int m = 3; m <= n_sqrt; m += 2) {
       if !(n % m) return 0;
    }
    return 1;
}

Somes other random remarks:

• Your indents looks crazy, maybe a formating issue.
• Also, you ask user to give number less than 1000, but you don't catch case where they don't respect this requirement.
• You never verify validity of your FILE*. Openings can fail.
• It's never asked to separate ints with comma in the 2nd file. Using just space should be fine.
• For the first file, if you move the first outputting out of the loop, you can get rid of the if...else statement.

Like this:

//...
fprintf(fptr, "%d",random[0]);
for (int i = 1; i < n; ++i) {
    fprintf(fptr,",%d",random[i]);
} 
//...

• I dont understand why you catch 0 < n < 3 in a different way
• You can write a function sorted_insert that put an int in a array in a sorted way.
• You can also compute prime check in the same loop. In fact, all the job can be made with an unique loop (plus one in sorted_insert and another in prime) but since I think it's a school assignment I let you find the rest by yourself.

Answer 2

Avoid recalculating

Lesser compilers will recalculate (int)sqrt((double)n) every iteration. Avoid that with a one time assignment.

//for (int k = 2; k <= (int)sqrt((double)n); ++k)
int sq = (int)sqrt((double)n)
for (int k = 2; k <= sq; ++k)

Avoid floating point math for integer problems

sqrt((double)n) of some perfect square may return a value very near the expected root. This is more common with 1) large n and lower quality sqrt() implementations. If that near value is just a tad small, the (int) will truncate away the x.9999999999... part to x and not x+1 leading to the wrong prime() functionality.

Also when the precision of int (think 64-bit) exceeds the precision of double, a similar unexpected result from sqrt() can arise.

There is fortunately a simple alternative that takes advantage that when a % b is calculated the additional cost of a / b is often trivial with modern compilers. So stop the loop when the quotient is too small.

//for (int k = 2; k <= (int)sqrt((double)n); ++k) {
//  if( n % k == 0) {
//   c = 1;
//  }
//}

int q = n-1;  // Insure all but n==2 iterates at least once
for (int k = 2; k <= q; ++k) {
  q = n/k; 
  if(n%k == 0) {
    c = 1;
    break; // leave for loop as subsequent iterations are not informative.
  }
}

Prime test can use the unsigned domain

Although OP is performing prime tests in a limited range, no need to code prime() with that limit.

Consider bool and other candidate ideas below.

#include <stdbool.h>

// Return true when prime 
bool prime(unsigned n) {
  if (n%2 == 0 || n == 1) {  // easy cases
    return n == 2;
  }
  unsigned quotient = n - 1;
  for (unsigned divisor = 3; divisor <= quotient; divisor += 2) {
    quotient = n / divisor;
    if( n % divisor == 0) {
      return false;
    }
  }
  return true;
}