Print the following pattern 1, 12, 123, 1235, 12357...

Problem Statement: Given an integer n, print the pattern.

Example 1:

Input: n = 5
Output:
1
1 2
1 2 3
1 2 3 5
1 2 3 5 7

Example 2:

Input: n = 6
Output:
1
1 2
1 2 3
1 2 3 5
1 2 3 5 7
1 2 3 5 7 11

Approach:

Firstly, we need to observe the pattern which is given. After carefully observing it is clear that that the pattern only contains prime numbers except 1, isn't it? So, we know that prime number starts from 2 so we will take a variable let's say k and initialize it to 2. Now we also know by looking at the pattern the pattern needs to be print until row and column becomes equal to given integer n. So, we will create an array list for storing the previous row numbers. And we know that the new number is always at last when row and columns are equal. So, we will check for the prime number with the help of function and print it and store in list and will increment k by 1 with the value obtained from function.
There are two methods used in this approach helper() and checkPrime(). helper() function helps in finding the appropriate prime number with the help of checkPrime() method. helper(k) takes k as parameter.

Algorithm:

Store 1 in any dynamic list and print

Intiailize k = 2

Run loop i from 1 until i < n

Inside this run loop j from 0 until j <= i

if i == j call method say helper() which will help in finding the appropriate next prime number value and store returned value from function in a variable say x.

print the prime number value i.e x.

Then do k = x + 1 (for searching the prime number after x)

Code Implementation:

Java

import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {
        int n = 5;

        // starting with first prime number i.e 2
        int k = 2;

        // for storing the previous row prime numbers
        ArrayList<Integer> ls = new ArrayList<>();

        // adding 1 to ls because every row starts from 1
        ls.add(1);
        // printing first row
        System.out.println(1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (i != j) {
                    System.out.print(ls.get(j) + " ");
                } else {
                    int x = helper(k);
                    ls.add(x);
                    System.out.println(x);
                    k = x + 1;
                }
            }
        }
    }

    // this method will give the next appropriate prime number
    public static int helper(int k) {
        if (checkPrime(k)) {
            return k;
        } else {
            return helper(k + 1);
        }
    }

    // method to check whether a number is prime or not
    public static boolean checkPrime(int n) {
        if (n <= 1)
            return false;
        if (n == 2)
            return true;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

Output:

1
1 2
1 2 3
1 2 3 5
1 2 3 5 7

Follow up: This approach can be further optimized using Sieve of Eratosthenes. Can you optimize it?

If you want to contribute such articles to solutions2coding.com please click here. Thank you!