New: 201 pattern programs with tested code in C, C++, Java and Python Explore patterns

Prime Number Triangle

Read summary with AI tools

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
  1. Output
  2. How the prime number triangle works
  3. Program in C
  4. Program in C++
  5. Program in Java
  6. Program in Python
  7. Time and space complexity
  8. Frequently asked questions

Prime Number Triangle output

Output (n = 5):

  2
  3  5
  7 11 13
 17 19 23 29
 31 37 41 43 47
Prime Number Triangle layout diagram, row by row (n = 5)
The numbers of the prime number triangle laid out row by row (n = 5).

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.

  1. Set candidate = 2.
  2. Run the outer loop for i from 1 to n.
  3. For each of the i places in the row, increase candidate until is_prime(candidate) is true.
  4. Print candidate three characters wide, then increase it by one.
  5. 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 <= x does that without a square root.
  • candidate never 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.

Authored by

Ghanendra Yadav runs Pattern Programs from Bangalore, India. The site started in 2020 to help students practise loops and logic through pattern programs in C, C++, Java and Python. Every program published here is compiled and run before it goes live, and the output shown is the real output.

Latest articles

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.