Why are the values of sum in both program different at the end?

Question

program 1.

#include<iostream>       
using namespace std;         
  int main()
{
int a[100000];
int *b=new int[1000000];
//for(int i=0;i<100000;i++)
 //a[i]=0;
long long int sum=0;
const long long int x=1000000000000ll;
for(long long int i=2;i<1000000;i++)
{

    if(b[i]==1)
    continue;
    for(long long int j=i*i;j<1000000;j+=i)
     b[j]=1;

    long long int k=((x-1)/i+1)*i-x;
//Sieve upto 10^12+10^5
for(;k<100000;k+=i)
  a[k]=1;   
}

for(int i=0;i<100000;i++)
{
    if(a[i]!=1)
    {
    cout<<i+x<<" "<<i%1000<<endl;
        sum=sum+i+x;


    }

}

cout<<"sum="<<sum;
}

In the second program when I am printing some values before printing sum then it is changing the value of sum in the program. Can anybody tell me why is this happening? program 2

#include<iostream>
   using namespace std;
  int main()
{
int a[100000];
int *b=new int[1000000];
//for(int i=0;i<100000;i++)
 //a[i]=0;
long long int sum=0;
const long long int x=1000000000000ll;
for(long long int i=2;i<1000000;i++)
{

    if(b[i]==1)
    continue;
    for(long long int j=i*i;j<1000000;j+=i)
     b[j]=1;

    long long int k=((x-1)/i+1)*i-x;
//Sieve upto 10^12+10^5
for(;k<100000;k+=i)
  a[k]=1;   
}

for(int i=0;i<100000;i++)
{
    if(a[i]!=1)
    {

        sum=sum+i+x;


    }

}

cout<<"sum="<<sum;
}

It looks like it is missing two values that I am going to sum. basically sum is the total of all prime numbers between 10^12 to 10^12+10^5

Answer 1

okay, I got the logic behind it, when I don't initialize array, it takes garbage values when might be 1 and 0 also, because was checking for

if(a[i] != 1)
{
  sum = sum + i + x;
}

so due to the a[i] == 1 that been put by garbage value, I was getting wrong answer. Run this to see 1 by garbage value

#include<iostream>

int main()
{
  int a[100000];
  for(int i = 0; i < 100000; i++)
    std::cout << a[i] << std::endl;
}

But still don't have no idea, why the cout statement corrected it??

Answer 2

When you create automatic array and dynamically allocated one in this code:

int a[100000];
int *b=new int[1000000];

they are unintialized. Later you read from b:

if(b[i]==1)

which leads to UB. You do assign some value to a in this code:

for(;k<100000;k+=i)
  a[k]=1;   
}

but it is not clear if all data is assigned. If not further reading from it leads to UB as well. You should initialize your data before using to eliminate UB and stop getting unpredictable results.

PS according to commented out code you tried to initialize a, but that would be not enough, b must be initialized as well.

Note: memory, allocated by new[] should be released by delete[], though that is not source of problem in your code. You better use std::vector which not only take care of memory allocation, but will properly initialize your data.