How to resolve the algorithm Pierpont primes step by step in the Java programming language

Published on 12 May 2024 09:40 PM
#Java

How to resolve the algorithm Pierpont primes step by step in the Java programming language

Table of Contents

Problem Statement

A Pierpont prime is a prime number of the form: 2u3v + 1 for some non-negative integers u and v .

A Pierpont prime of the second kind is a prime number of the form: 2u3v - 1 for some non-negative integers u and v .

The term "Pierpont primes" is generally understood to mean the first definition, but will be called "Pierpont primes of the first kind" on this page to distinguish them.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Pierpont primes step by step in the Java programming language

This code generates and displays Pierpont primes of the first and second kinds up to a specified limit.

Key implementation details:

  1. pierpontPrimes Function:

    • It takes two parameters:
      • n: The number of Pierpont primes to generate.
      • first: A boolean indicating whether to generate primes of the first or second kind.
    • It generates a list of prime numbers using a modified version of the Sieve of Eratosthenes algorithm.
    • It starts with a list of numbers from 2 up to n (inclusive).
    • It identifies prime candidates by removing multiples of 2 and 3 from the list.
    • It then checks if the remaining candidates are prime numbers using the BigInteger.isProbablePrime method.
    • It returns a list of Pierpont primes.

  2. Prime Generation Algorithm:

    • The algorithm uses two helper variables, twoTest and threeTest, to keep track of the current multiples of 2 and 3 being checked against.
    • It maintains a list of "two-smooth" numbers, which are numbers that have only 2 or 3 as factors.
    • The algorithm finds the smallest number in the list of "two-smooth" numbers.
    • If the smallest number is a multiple of 2, the corresponding multiple of 2 in the list of numbers is removed.
    • If the smallest number is a multiple of 3, the corresponding multiple of 3 in the list of numbers is removed.
    • The algorithm then checks if the next number in the list (after the smallest "two-smooth" number) is prime.
    • If it is prime, it adds it to the list of Pierpont primes and increments the count.
    • The algorithm continues this process until the desired number of Pierpont primes is found.

  3. Display Function:

    • display is a helper function used to display the generated Pierpont primes.
    • It takes two parameters:
      • message: A message to be displayed before the primes.
      • primes: A list of Pierpont primes.
    • It formats the numbers using NumberFormat and prints them in a table-like format.

Source code in the java programming language

import java.math.BigInteger;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;

public class PierpontPrimes {

    public static void main(String[] args) {
        NumberFormat nf = NumberFormat.getNumberInstance();
        display("First 50 Pierpont primes of the first kind:", pierpontPrimes(50, true));
        display("First 50 Pierpont primes of the second kind:", pierpontPrimes(50, false));
        System.out.printf("250th Pierpont prime of the first kind:     %s%n%n", nf.format(pierpontPrimes(250, true).get(249)));
        System.out.printf("250th Pierpont prime of the second kind: %s%n%n", nf.format(pierpontPrimes(250, false).get(249)));
    }
    
    private static void display(String message, List<BigInteger> primes) {
        NumberFormat nf = NumberFormat.getNumberInstance();
        System.out.printf("%s%n", message);
        for ( int i = 1 ; i <= primes.size() ; i++ ) {
            System.out.printf("%10s  ", nf.format(primes.get(i-1)));
            if ( i % 10 == 0 ) {
                System.out.printf("%n");
            }
        }
        System.out.printf("%n");
    }

    public static List<BigInteger> pierpontPrimes(int n, boolean first) {
        List<BigInteger> primes = new ArrayList<BigInteger>();
        if ( first ) {
            primes.add(BigInteger.valueOf(2));
            n -= 1;
        }

        BigInteger two = BigInteger.valueOf(2);
        BigInteger twoTest = two;
        BigInteger three = BigInteger.valueOf(3);
        BigInteger threeTest = three;
        int twoIndex = 0, threeIndex = 0;
        List<BigInteger> twoSmooth = new ArrayList<BigInteger>();

        BigInteger one = BigInteger.ONE;
        BigInteger mOne = BigInteger.valueOf(-1);
        int count = 0;
        while ( count < n ) {
            BigInteger min = twoTest.min(threeTest);
            twoSmooth.add(min);
            if ( min.compareTo(twoTest) == 0 ) {
                twoTest = two.multiply(twoSmooth.get(twoIndex));
                twoIndex++;
            }
            if ( min.compareTo(threeTest) == 0 ) {
                threeTest = three.multiply(twoSmooth.get(threeIndex));
                threeIndex++;
            }
            BigInteger test = min.add(first ? one : mOne);
            if ( test.isProbablePrime(10) ) {
                primes.add(test);
                count++;
            }
        }
        return primes;
    }
    
}

You may also check:How to resolve the algorithm System time step by step in the Retro programming language
You may also check:How to resolve the algorithm Natural sorting step by step in the Elixir programming language
You may also check:How to resolve the algorithm Ramanujan primes/twins step by step in the Sidef programming language
You may also check:How to resolve the algorithm String comparison step by step in the Sidef programming language
You may also check:How to resolve the algorithm Array length step by step in the Haskell programming language