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

×

YCCE02 - Editorial

PROBLEM LINKS

Practice
Contest

Author:

SRIKANT BADRI

DIFFICULTY:

SIMPLE

PREREQUISITES:

Concept of Prime

PROBLEM:

To find all prime numbers upto 10^7

EXPLANATION:


To gain 100 points one must know an efficient algorithm to evaluate prime numbers upto 10^7 in 1 sec. One such algorithm is Sieve Of Eratosthenes.

The approach used by this algorithm is:
Step 1:Create a bool arrray having size 10000000.
Step 2:Initialize every value of that array with true & initialize index 0,1 as false since they are not primes. (You can use memset function in C,C++ for this)
Step 3: Pick a number from bool array which is not false.
Step 4: Make all multiples of that number in the array as false.
Step 5: Repeat step 3 & 4 until all the elements (<=10000000) having true value have not been considered.
Step 6: All the elements having true values are primes.
The code for above algorithm is:

bool Primes[10000003];  
long long int i,j;
memset(Primes,true,sizeof(Primes));
Primes[0]=false;
Primes[1]=false;
for(i=2;i<=10000000;i++)
{
if(Primes[i])
{
for(j=i*2;j<=10000000;j+=i)
{
Primes[j]=false;
}
}
}

SAMPLE SOLUTION:


Author

asked 09 Oct '16, 21:58

shrikantbadri's gravatar image

1★shrikantbadri
304
accept rate: 9%

edited 10 Oct '16, 13:35

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×301
×199
×2

question asked: 09 Oct '16, 21:58

question was seen: 477 times

last updated: 10 Oct '16, 13:35