TSECJC02 - Editorial

PROBLEM LINK:

Practice

Contest

Author: tseccodecell

DIFFICULTY:

Easy

PREREQUISITES:

Primality test

PROBLEM:

Given the first two numbers of a sequence F1 and F2, you have to generate a sequence such that F_{i+2}=F_{i+1}+F_i. You have to find the number of prime numbers from F1 to F20.

QUICK EXPLANATION:

Generate the 20 numbers. Count the number of prime numbers among these using a primality test.

EXPLANATION:

Generate the sequence using a simple loop. Only the last two values in the sequence need to be stored. As the numbers are being generated, check for primality and adjust the counter. Note: Also check the first two numbers which are given as input.

For checking whether a number is prime or not, a simple loop which tests whether a number n is divisible with any number till \sqrt{n} should suffice.

A faster solution is to use Sieve of Eratosthenes. First, make a boolean array of size N, initialising all the values as false. N is the value till which we want to check for primes (10^6 should suffice). Starting from 2, check every multiple of 2 and mark it as true. After that, consider the next value of 2 which is still marked as false, 3. Mark all multiples of 3 as true. Since 4 is marked true, we skip it and move on to 5. We mark all multiples of 5 as true. We continue doing this till \sqrt{N} (10^3 if N=10^6).

Other efficient primality tests can also be used to solve the problem.

SOLUTION:

Author’s

Tester’s

//