You are not logged in. Please login at www.codechef.com to post your questions!

×

runtime error in ALGPRX

i'm getting runtime error(SIGSEV) in problem ALGPRX. Help me anyone. Here is my code.

asked 30 Jul '14, 18:55

mayankb_03's gravatar image

1★mayankb_03
115621
accept rate: 16%


Since U<10^6, you have to assign memory outside main....Even then your code will not get accepted because ,,,it is too slow....for every test case ,,you are calculating all the prime nos upto 'U' .You are actually repeating the work already done.

A more better approach would be ,

Declare bool array [10^6],long long int sum[10^6] outside main.

Now using sieve of erastotehenes algo or any other good primality testing algo...update the bool array.

If(i=prime)then bool[i]=true, else false.

Now update the sum array..sum[i]=Sum of all primes less than i.

Now for each test case you can easily read from the sum array and update the answer as sum[U]. This code time complexity would roughly be O(10^7+N),where N is the no of test cases, which will compile under the time limit easily..If you find this post helpful upvote and mark it as accepted answer...CHEERS HAPPY CODING :).

link

answered 31 Jul '14, 11:47

prem_93's gravatar image

3★prem_93
6233816
accept rate: 19%

edited 31 Jul '14, 11:48

Upper bound for given input is U<10^6. Assign memory outside main(global scope).

int prime[1000006];

int main()

{

//insert code here

return 0;

}

link

answered 30 Jul '14, 22:45

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1

question asked: 30 Jul '14, 18:55

question was seen: 276 times

last updated: 31 Jul '14, 11:48

Related questions