Getting segmentation fault for the whole range (if i reduce num it gets fixed)

#1

#include
using namespace std;

int main() {
long long int num, val;
cin>>val;
num = 5000000;
int arr[num] = {0};
cout<<endl;
arr[2] = 1;
//mark all odd numbers as prime
for(int i=3; i<num; i = i+2)
{ arr[i]=1; }
//as 1 prime of 2 already accounted
for(int i=2; i<num; i++)
{
if(arr[i]==0){continue;}
val–;
if(val==0){cout<<i<<endl; return 0; }
for(int j=i*i;j<num;j=j+i)
{arr[j]=0;}
}
return 0;
}

#2

The 5,000,000th prime is 86,028,121.

so atleast this much space you require

as size of array is long and you need to save only 1 or 0
so rather than int use bool arr[100000001]={};

i hope this helps

#3

I am still getting segmentation faults.

#4

Kindly let me know, as almost all number theory questions are around such prime numbers and keep failing due the same reason.

#5

Firstly make bool array
And iterate only to odd numbers

After doing these modifications send me link of your code
I will help you

#6

#include
using namespace std;

int main() {
long long int num, val;
cin>>val;
num = 100000001;
bool arr[num] = {0};
cout<<endl;
arr[2] = 1;
//mark all odd numbers as prime
for(int i=3; i<num; i = i+2)
{ arr[i]=true; }
//as 1 prime of 2 already accounted
for(int i=3; i<num; i=i+2)
{
if(not arr[i]){continue;}
val–;
if(val==0){cout<<i<<endl; return 0; }
for(int j=i*i;j<num;j=j+i)
{arr[j]=false;}
}
return 0;
}

#7 
#include <iostream>
#include <vector>
using namespace std;
#define ll long long int
bool arr[100000004] = {0};
vector<int>prime;
int main() {
    // freopen("input.txt","r",stdin);
    ll num, val;
    cin >> val;
    num = 100000001;
    // cout << endl;
    arr[2] = 1;
    prime.push_back(2);
    //mark all odd numbers as prime
    for (ll i = 3; i < num; i = i + 2)
    { arr[i] = true; }
    //as 1 prime of 2 already accounted
    for (ll i = 3; i < num; i = i + 2)
    {
        // if (not arr[i]) {continue;}
        // val--;
        // if (val == 0) {cout << i << endl; return 0; }
        if (arr[i]) {
            prime.push_back(i);
            for (ll j = i * i; j < num; j = j + i)
            arr[j] = false;
        }
    }
    cout<<prime[val-1];
    return 0;
}

this is modified code and passing all testcase

i hope this help
if you have more doubts regarding this feel free to ask
if your doubt is resolved mark it as resolved from your doubt section inside your course

#8

I still get a TLE.

image
image999×784 40.7 KB

#9

instead of true and false use 0 and 1 then
all testcase are passing

#include <iostream>
#include <vector>
using namespace std;
#define ll long long int
bool arr[100000004] = {0};
vector<int>prime;
int main() {
    // freopen("input.txt","r",stdin);
    ll num, val;
    cin >> val;
    num = 100000001;
    // cout << endl;
    arr[2] = 1;
    prime.push_back(2);
    //mark all odd numbers as prime
    for (ll i = 3; i < num; i = i + 2)
    { arr[i] = 1; }
    //as 1 prime of 2 already accounted
    for (ll i = 3; i < num; i = i + 2)
    {
        // if (not arr[i]) {continue;}
        // val--;
        // if (val == 0) {cout << i << endl; return 0; }
        if (arr[i]) {
            prime.push_back(i);
            for (ll j = i * i; j < num; j = j + i)
            arr[j] = 0;
        }
    }
    cout<<prime[val-1];
    return 0;
}
#10

Still getting TLE. I copied the exact same code you have give to check it out in the challenges.
Where are you running it to get all test cases to pass?

#11

Sorry
actually the code which pass testcase is

#include <iostream>
#include <vector>
using namespace std;
#define ll long long int
bool arr[100000004];
vector<int>prime;
int main() {
    // freopen("input.txt","r",stdin);
    ll num, val;
    cin >> val;
    num = 100000001;
    // cout << endl;
    arr[2] = true;
    prime.push_back(2);
    //mark all odd numbers as prime
    for (ll i = 3; i < num; i = i + 2)
    { arr[i] = true; }
    //as 1 prime of 2 already accounted
    for (ll i = 3; i < num; i = i + 2)
    {
        // if (not arr[i]) {continue;}
        // val--;
        // if (val == 0) {cout << i << endl; return 0; }
        if (arr[i]) {
            prime.push_back(i);
            for (ll j = i * i; j < num; j = j + i)
            arr[j] = false;
        }
    }
    cout<<prime[val-1];
    return 0;
}

i have just copy paste above code and make changes
sorry for inconvenience caused

#12

It working now thanks.
To understand this TLE problem better, you solved it by:

  1. Replacing all 0/1 (integers) with true/false. This I understand.
    Along with you also removed the {0} initialization from the array initialize? Does this have an effect?
  2. The if loop I had in my code was with the intention of now running the complete for loop. I thought it would save time.
    But you replaced it with the use of a vector? Is it faster than running those arithmetic and if-else command? and why?
#13

The major change which i done is

  1. make array global
    Reason
    actually when you have declared that array in function it was created in stack memory and when you were printing something compiler got some time and releases some memory which helped in processing and printing the output.
    Its resolved by creating the array globally because the global arrays are created in heap memory.

  2. instead of int use ll(long long int) this is required as n is large

  3. using vector
    this is not to optimise
    actually intially i did not understand your approach and also it is giving wrong answer that’s why i use vector
    but now when i see again i got your mistake
    you can also use your appoach also

Modified Code

#include<iostream>
using namespace std;
#define ll long long int
bool arr[100000004];
int main() {
    ll num, val;
    cin >> val;
	if(val==1){cout<<2<<endl;return 0;}
    num = 100000001;
    arr[2] = 1;
	val--;
//mark all odd numbers as prime
    for (ll i = 3; i < num; i = i + 2)
    { arr[i] = 1; }
//as 1 prime of 2 already accounted
    for (ll i = 3; i < num; i = i + 2)
    {
        if (!arr[i]);
        else{val--;
        if (val == 0) {cout << i << endl; return 0; }
        for (ll j = i * i; j < num; j = j + i)
        {arr[j] = 0;}}
    }
    return 0;
}

and this time it is same code which passing testcase :innocent:

i hope this help
if you have more doubts regarding this feel free to ask
if your doubt is resolved mark it as resolved from your doubt section inside your course