Prime Sum C program !! Dynamically allocated memory Let P(n) denote the sum of t

Question

Prime Sum C program !! Dynamically allocated memory
Let P(n) denote the sum of the first n prime numbers. For example, P(1) = 2 and P(3) = 10, since the first three prime numbers are 2, 3 and 5, respectively. Write a program to determine the value of the function P(n) for different values of n. The first few prime sums are 2, 5, 10, 17, 28, 41, 58 and 77. Input The first line of the input file contains a single positive integer, t (t 20000), representing the number of test cases.
The following t lines contain one positive integer n (n 10000), representing the prime sum to be computed for the case. Output Write out a single integer on a line by itself for each test case, indicating P(n), for the corresponding input value n.
Sample Input
3
1
6
8
Sample Output
2
41
77
Assignment Details
Even though this assignment can be coded with statically allocated arrays, please write your solution using dynamically allocated arrays.
(Your programs should have either malloc/calloc calls, as well as a call to free.)
In order to efficiently generate the first 10000 primes, please use the Sieve of Eratosthenes. From there, just generate each of the prime sums instead of recomputing for each test case.

Explanation / Answer

The following C code prints the sum of "n" prime numbers using a dynamic array.

There is one hash define (#define LIMIT 10000), that can be replaced by unsigned long LIMIT if the number of prime numbers needed is greater than 6 (then, according to Rosser's theorem, LIMIT would be n*log(n)+n*log(log(n))).

Compile the source code using -lm option as math.h is included.

$ gcc -lm sourceCode.c

Source code:

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

#define LIMIT 10000
//unsigned long LIMIT;

void sieve_of_eratosthenes(int P[], int n){
int i;
int j;

for(i=2; i<LIMIT; i++)
    if(P[i])
      for(j=i; i*j<LIMIT;j++)
        P[i*j]=0;
}

int main()
{
    int N=0; //Number
    int T=0; //Test case
    int sum=0; //Sum of prime numbers
    int *P;
    int i;
    int count;
   
    scanf("%d",&T);
  
    while(T--){
       scanf("%d",&N);

        // The following line only works if N>6.
        //LIMIT=N*log(N)+ (N*log(log(N)));

        P = (int *)malloc((sizeof(int)*LIMIT)+1);
        
        if(P==NULL){
            printf("Error! Memory not allocated!");
            exit(0);
        }

        // All values in P are initialized by 1 (index 2 to N)
        for(i=2; i<=LIMIT; i++)
            P[i]=1;

       sieve_of_eratosthenes(P, N);

        count=0; sum=0;
        for(i=2; i<=LIMIT; i++){
          if(P[i]){
            count++;
            sum+=i;
            if(count>=N)
              break;
          }
        }
        free(P);
       printf("%d ",sum);
    }
  
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.