### PROBLEM LINK:

**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].