I am a sort of newbie to programming (actually coming back to it after a gap of 20 yrs :) ). I am trying to make a program for a question on project euler, to find sum of all prime numbers under 2 million. I am trying to use the Eratosthenes sieve algorithm. I am using code::blocks with GNU GCC compiler.
#include <stdio.h>
#define L 2000000
int main()
{
unsigned long long int i, j, n, num[L], sum = 0;
for (i = 0; i < L; i++)
num[i] = i + 1;
for (j = 2; j*j <=L; j++)
{
for (n = j; n*j<=L; n++)
{
num[n * j - 1] = 0;
}
}
for (i = 1; i < L; i++)
{
if (num[i] != 0)
{
printf("%llu\n",num[i]);
sum = sum + num[i];
}
}
printf("%llu\n", sum);
return 0;
}
The program works for all values of L below 1000000, but stops working above that. Also I get warning about the long long int as follows:
***||=== Build file: Debug in 2MILLIONPRIMESUM (compiler: GNU GCC Compiler) ===|
***E:\Code Blocks Projects\2MILLIONPRIMESUM\main.c||In function 'main':|
E:\Code Blocks Projects\2MILLIONPRIMESUM\main.c|22|warning: unknown conversion type character 'l' in format [-Wformat=]|
E:\Code Blocks Projects\2MILLIONPRIMESUM\main.c|22|warning: too many arguments for format [-Wformat-extra-args]|******
I get similar warnings when trying to use "long double" etc. Is this a problem with the compiler, that it cannot handle long long and long double?
The above code works without any warning (only for L <=1000000) on GDB online compiler. Request everyone to advise me on the above issues. Thank you so much in advance.
As pointed out in comments, 2000000 * sizeof(long long) is too large of an array to fit on the stack; confidence is high that this is the root cause of the issue.
That said, the code works nicely when we add the dynamic memory allocation of num as shown below in the line having malloc(). We also added code to ensure the memory allocation was successful. If not, a printf() is there to alert the user, and then the program exits harmlessly.
This code was compiled and run/checked by me before posting.
EDIT: I ran one more test just now with sum as type double -- the final answer is still the same: 142913828922. This tends to support the notion that the code is working per design and requirement.
#include <stdio.h>
#include <stdlib.h>
#define L 2000000
int main()
{
unsigned long long int i, j, n, sum = 0;
unsigned long long int *num = malloc( L * sizeof(unsigned long long int));
if(!num)
{
printf("malloc() failed!\n");
return 0;
}
for (i = 0; i < L; i++)
num[i] = i + 1;
for (j = 2; j*j <=L; j++)
{
for (n = j; n*j<=L; n++)
{
num[n * j - 1] = 0;
}
}
for (i = 1; i < L; i++)
{
if (num[i] != 0)
{
printf("%llu\n",num[i]);
sum = sum + num[i];
}
}
printf("%llu\n", sum);
/* As you malloc(), so shall you free()! (thank you Fe2O3): */
free(num);
return 0;
}
Output:
...
...
1999733
1999771
1999799
1999817
1999819
1999853
1999859
1999867
1999871
1999889
1999891
1999957
1999969
1999979
1999993
142913828922
This 2nd version may interest you: per discussion with Fe2O3 in comments, it was revealed that the num array need not occupy a long long data type; that the range of num array will fit neatly into a 32-bit int.
Furthermore, upon reflection, it was realized that such a change invites a considerable space savings. So much so that perhaps the adapted num array may now fit on the stack!
This notion seems to be born out per the runnable code here.
Conspicuously absent from the code is any hint of malloc(), and yet we're getting competent results per the featured Output:
#include <stdio.h>
#include <stdlib.h>
#define L 2000000
int main()
{
unsigned long long int sum = 0;
unsigned int i, j, n, num[L];
for (i = 0; i < L; i++)
num[i] = i + 1;
for (j = 2; j*j <=L; j++)
{
for (n = j; n*j<=L; n++)
{
num[n * j - 1] = 0;
}
}
for (i = 1; i < L; i++)
{
if (num[i] != 0)
{
if(i > L-200) /* just print last XX of array*/
printf("%llu\n",num[i]);
sum = sum + num[i];
}
}
printf("%llu\n", sum);
printf("sizeof(int): %u\nsizeof(num): %u\n", sizeof(int), sizeof(num));
return 0;
}
Output:
1999817
1999819
1999853
1999859
1999867
1999871
1999889
1999891
1999957
1999969
1999979
1999993
142913828922
sizeof(int): 4
sizeof(num): 8000000
Nice thing about Stackverflow community is that they'll bring ideas to the table that challenge and grow you. Both Fe2O3 and Jonathan Leffler mentioned using bits for even more space savings. (Wut?) At last I've worked it out...
Here is version 3.0 for the world -- only puts about 240K on the stack -- nice! That's a long way from the 2 terrabytes we started with. (j/k -- was actually 2M * 64bits = 15.25MB)
Runnable code is here.
#include <stdio.h>
#include <string.h> /* memset */
#define L 2000000
/* These one-line bit ops are a compromise between a macro and a function */
static void clear_bit(unsigned char *x, int bitNum) { *x &= ~(1L << bitNum); }
static int test_bit(unsigned char x, int bitNum) { return !!(x & (1L << (bitNum))); }
static void set_bit(unsigned char *x, int bitNum) { *x |= (1L << bitNum); } /* unused */
int main()
{
unsigned long i=8, j, n;
unsigned char bits[L/8];
unsigned long long int sum = 0;
/* Set all the bits of the array to 1. Replaces step in old code
* where we filled the array with num = index + 1 */
memset(bits, 255, sizeof(bits));
/* This is the section where we *disqualify* non-prime entries by
* clearing the related bit. Formerly we set the index to zero.*/
for (j = 2; j*j <= L; j++)
{
for (n = j; n*j <= L; n++)
{
long num = n * j;
clear_bit(&bits[num/8], num%8);
}
}
/* In this section we'll do a print out and get the sum as before... */
for (i = 2; i < L; i++)
{
if (test_bit(bits[i/8], (i%8)) != 0)
{
if(i > L-200) /* just print last XX of array*/
printf("%lu\n", i );
sum += i;
}
}
/*should say 142913828922 (142,913,828,922)*/
printf("%lld\n", sum);
return 0;
}
Output:
1999817
1999819
1999853
1999859
1999867
1999871
1999889
1999891
1999957
1999969
1999979
1999993
142913828922
Here is version 4.0 -- only puts about 122K on the stack.
The bit array is halved since v3.0. Thanks again to the
SO community for the inspiration -- please see comments
for more, and the algo optimizations from Fe2O3.
Runnable code is here.
#include <stdio.h>
#include <string.h> /* memset */
#define L 2000000
static void clear_bit(unsigned char *x, int bitNum) { *x &= ~(1L << bitNum); }
static int test_bit(unsigned char x, int bitNum) { return !!(x & (1L << (bitNum))); }
int main()
{
unsigned long i, j, n;
unsigned char bits[L/16]; /* Only 125,000 bytes! */
unsigned long long sum = 0;
/* Set all the bits of the array to 1. */
memset(bits, 255, sizeof(bits));
/* Disqualify non-prime entries by clearing the related bit.
* Small note on how bit array is accessed:
In an odd-numbers-only bit buffer, addressing is:
bits[0] represents numbers: 1, 3, 5, 7, 9, 11,13,15
bits[1] represents numbers: 17,19,21,23,25,27,29,31
bits[2] represents numbers: 33,35,37,39,41,43,45,47
...
Hence, the math is:
bit array offset = number/16;
Representative bit = (number%16)/2
*/
for (j = 2; j*j <= L; j++)
{
for (n = j; n*j <= L; n++)
{
long num = n * j;
long offset = num/16;
if(num%2) /* if odd */
clear_bit(&bits[offset], (num%16)>>1 );
}
}
/* Print out and sum: 2 will be a special case because it is the only
* even prime number in the universe. Per our algo, we store no even
* numbers. Hence, 2 (and its printing, if desired) is done manually. */
sum = 2; /* Primes start here */
for(i = 3; i < L; i+=2) /* Now process the remaining primes... */
{
long offset = i/16;
if(test_bit(bits[offset], (i%16)>>1 ) != 0)
{
if(i > L-200) /* just print last XX of array*/
{
printf("%lu\n", i );
}
sum += i;
}
}
/*should say 142913828922 (142,913,828,922). */
printf("%llu\n", sum);
return 0;
}
Output:
1999817
1999819
1999853
1999859
1999867
1999871
1999889
1999891
1999957
1999969
1999979
1999993
142913828922
My 2 cents for version 5.0:
L, defaults to 2000000unsigned long for all computationsbits array now allocated and initialized to 0, indicates composite numbersChqrlie.
#include <stdio.h>
#include <stdlib.h>
static void set_bit(unsigned char *x, int bitNum) { *x |= 1 << bitNum; }
static int test_bit(unsigned char x, int bitNum) { return (x >> bitNum) & 1; }
int main(int argc, char *argv[])
{
unsigned long L = argc > 1 ? strtol(argv[1], NULL, 0) : 2000000;
unsigned long i, j, n;
unsigned char *bits = calloc(1, L / 16 + 1); /* Only 125,000 bytes! */
unsigned long long sum;
if (!bits) {
fprintf(stderr, "out of memory\n");
return 1;
}
/* Disqualify non-prime entries by clearing the related bit.
* Small note on how bit array is accessed:
in an odd-numbers-only bit buffer, addressing is:
bits[0] represents numbers: 1, 3, 5, 7, 9, 11,13,15
bits[1] represents numbers: 17,19,21,23,25,27,29,31
bits[2] represents numbers: 33,35,37,39,41,43,45,47
...
Hence, the math is:
bit array offset = number / 16;
representative bit = (number % 16) / 2
*/
for (j = 3; j * j <= L; j += 2)
{
for (n = j * j; n <= L; n += 2 * j)
{
unsigned long offset = n / 16;
set_bit(&bits[offset], (n % 16) >> 1);
}
}
/* Print out and sum: 2 will be a special case because it is the only
* even prime number in the universe. Per our algo, we store no even
* numbers. Hence, 2 (and its printing, if desired) is done manually. */
sum = 2; /* Primes start here */
for (i = 3; i <= L; i += 2) /* Now process the remaining primes... */
{
unsigned long offset = i / 16;
if (!test_bit(bits[offset], (i % 16) >> 1))
{
sum += i;
if (i > L - 200) /* just print last XX of array*/
{
printf("%lu\n", i);
}
}
}
/*should say 142913828922 (142,913,828,922). */
printf("%llu\n", sum);
free(bits);
return 0;
}
Output (13ms total time):
1999817
1999819
1999853
1999859
1999867
1999871
1999889
1999891
1999957
1999969
1999979
1999993
142913828922