The prime number triangle prints the primes in order, one on the first row, two on the second, and so on. Five rows need the first fifteen primes, from 2 to 47.
Quick answer: Write a small is_prime function that tries divisors from 2 up to the square root of the number. Keep a candidate that starts at 2. For each place in the triangle, move candidate forward until it is prime, print it, then add one so the same prime is not printed twice. The rows grow like a right triangle: row i holds i primes.
This program is part of the Series Patterns collection.
Table of contents8 sections
Prime Number Triangle output
Output (n = 5):
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

How the prime number triangle works
The loops are the same as for any right triangle of numbers. The work is in finding the next prime. The program keeps one number, candidate, that only ever moves forward. Whenever the triangle needs a number, the while loop skips over non-primes until it reaches a prime. Testing divisors only up to the square root is enough: if x had a divisor larger than its square root, it would also have a matching one below it.
- Set
candidate = 2. - Run the outer loop for
ifrom 1 ton. - For each of the
iplaces in the row, increasecandidateuntilis_prime(candidate)is true. - Print
candidatethree characters wide, then increase it by one. - Move to the next line after the row.
Key takeaways
- A helper function keeps the prime test out of the loops, which makes both easier to read.
- Divisors only need to be tried up to √x; the loop condition
d * d <= xdoes that without a square root. candidatenever goes back, so each number is tested at most once.- 1 is not prime, so the test returns false for anything below 2.
Prime Number Triangle in C
#include <stdio.h>
int is_prime(int x) {
if (x < 2)
return 0;
for (int d = 2; d * d <= x; d++)
if (x % d == 0)
return 0;
return 1;
}
int main(void) {
int n = 5;
int candidate = 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
while (!is_prime(candidate))
candidate++;
printf("%3d", candidate);
candidate++;
}
printf("\n");
}
return 0;
}Prime Number Triangle in C++
#include <iostream>
#include <iomanip>
using namespace std;
bool isPrime(int x) {
if (x < 2)
return false;
for (int d = 2; d * d <= x; d++)
if (x % d == 0)
return false;
return true;
}
int main() {
int n = 5;
int candidate = 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
while (!isPrime(candidate))
candidate++;
cout << setw(3) << candidate;
candidate++;
}
cout << endl;
}
return 0;
}Prime Number Triangle in Java
public class PrimeNumberTriangle {
static boolean isPrime(int x) {
if (x < 2)
return false;
for (int d = 2; d * d <= x; d++)
if (x % d == 0)
return false;
return true;
}
public static void main(String[] args) {
int n = 5;
int candidate = 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
while (!isPrime(candidate))
candidate++;
System.out.printf("%3d", candidate);
candidate++;
}
System.out.println();
}
}
}Prime Number Triangle in Python
def is_prime(x):
if x < 2:
return False
d = 2
while d * d <= x:
if x % d == 0:
return False
d += 1
return True
n = 5
candidate = 2
for i in range(1, n + 1):
for j in range(i):
while not is_prime(candidate):
candidate += 1
print(f"{candidate:3d}", end="")
candidate += 1
print()Time and space complexity
Testing a number x takes up to √x divisions. The triangle uses the first n(n + 1) / 2 primes, so the work grows a little faster than O(n²). Memory stays at O(1).
Frequently asked questions
Why test divisors only up to the square root?
Divisors come in pairs: if 91 = 7 × 13, one of the pair is at most √91 ≈ 9.5. So if no number from 2 to √x divides x, nothing larger will either. Writing the test as d * d <= x avoids floating-point square roots altogether.
Is 1 a prime number?
No. A prime has exactly two different divisors, 1 and itself, and 1 has only one. That is why the function returns false for any x below 2, and why the triangle starts at 2.
How can I make it faster for many rows?
For a large triangle, build a list of primes first with the sieve of Eratosthenes and then print from the list. The sieve finds every prime up to a limit in about O(m log log m) time, which beats testing each number separately.
Can I print only the primes in a pyramid shape?
Yes. Add n − i spaces at the start of each row, as in the number pyramid, and print each prime with one space after it instead of a fixed width.










