PROBLEM LINK:
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.