PRLIN - Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Aakash Jain
Tester: Aakash Jain
Editorialist: Aakash Jain

DIFFICULTY:

SIMPLE

PREREQUISITES:

High-school math

PROBLEM:

Find the sum of all prime numbers occurring on the Nth row of the number triangle:

1
2 3
4 5 6
7 8 9 10
...

QUICK EXPLANATION:

Find the first number of the Nth row, which will be one more than the sum of first N-1 natural numbers. Starting at this number, test N consecutive numbers for primality and find their sum.

EXPLANATION:

The first number on the Nth row of this triangle will be one more than the sum of first N-1 natural numbers. For example, the 4th row: the sum of first 3 natural numbers is 1+2+3 = 6, and 6+1 = 7, which is the first number on the 4th row.

The last number on the row will be N-1 more than the first, since the Nth row contains N numbers.

first = (N*(N-1)/2) + 1
last = first + N - 1
Now each number **x** in this range must be tested for primality. We can do this by checking for factors of x in the closed range **[2, sqrt(x)]**. If any such factor exists, x is not prime. The following pseudo-code explains the procedure: ``` function isPrime(x) if x <= 1 return false for i = 2 to x if x%i == 0 return false return true ``` Now each prime number must be added to our answer: ``` sum = 0 for i = first to last if isPrime(i) sum += i ``` ### AUTHOR'S SOLUTION: Author's solution can be found [here][333].