How to resolve the algorithm Consecutive primes with ascending or descending differences step by step in the Java programming language

Published on 12 May 2024 09:40 PM
#Java

How to resolve the algorithm Consecutive primes with ascending or descending differences step by step in the Java programming language

Table of Contents

Problem Statement

Find and display here on this page, the longest sequence of consecutive prime numbers where the differences between the primes are strictly ascending. Do the same for sequences of primes where the differences are strictly descending.

In both cases, show the sequence for primes   <   1,000,000.

If there are multiple sequences of the same length, only the first need be shown.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Consecutive primes with ascending or descending differences step by step in the Java programming language

Purpose:

The Java code identifies the longest consecutive runs of ascending and descending gaps between prime numbers within a given limit.

Code Structure:

1. Main Method:

  • It sets the limit for prime number search as 1 million.
  • Calls listPrimeNumbers to generate a list of prime numbers up to the limit.
  • Initializes lists asc and desc to track ascending and descending gaps, and maxAsc and maxDesc to store the max-length gaps.
  • Initializes maxAscSize and maxDescSize to keep track of the maximum gap sizes.
  • Iterates through the prime numbers, adding them to the asc or desc list based on the differences between them.
  • Updates the maxAsc and maxDesc lists if the current gap size exceeds the maximum.

2. listPrimeNumbers Method:

  • Uses the Sieve of Eratosthenes to generate a list of prime numbers up to the given limit.
  • Returns the list of prime numbers.

3. displayResult Method:

  • Prints the prime numbers in the list, with the gaps between them in parentheses.
  • Prints newline characters to format the output.

Algorithm:

The algorithm checks each prime number and determines if it continues an ascending or descending gap sequence in the asc or desc lists. If the gap size exceeds the previous gap, it starts a new gap sequence. The maxAsc and maxDesc lists store the longest ascending and descending gap sequences found.

Output:

The output displays the longest consecutive runs of ascending and descending prime gaps within the given limit. For example, for a limit of 1 million:

Output:

Longest run(s) of ascending prime gaps up to 1000000:
3 (2) 5 (2) 7 (2) 11 (2) 13 (2) 17 (2) 19
3 (2) 5 (2) 7 (2) 11 (2) 13 (2) 17 (2) 19 (2) 23

Longest run(s) of descending prime gaps up to 1000000:
19 (2) 17 (2) 13 (2) 11 (2) 7 (2) 5 (2) 3
17 (2) 13 (2) 11 (2) 7 (2) 5 (2) 3

Source code in the java programming language

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public final class ConsecutivePrimes {

	public static void main(String[] aArgs) {
		final int limit = 1_000_000;
		List<Integer> primes = listPrimeNumbers(limit);
		
		List<Integer> asc = new ArrayList<Integer>();
		List<Integer> desc = new ArrayList<Integer>();
		List<List<Integer>> maxAsc = new ArrayList<List<Integer>>();
		List<List<Integer>> maxDesc = new ArrayList<List<Integer>>();
	    int maxAscSize = 0;
	    int maxDescSize = 0;
	    
	    for ( int prime : primes ) {
	   	    final int ascSize = asc.size();
	        if ( ascSize > 1 && prime - asc.get(ascSize - 1) <= asc.get(ascSize - 1) - asc.get(ascSize - 2) ) {
	            asc = new ArrayList<Integer>(asc.subList(ascSize - 1, asc.size()));
	        }	        
	        asc.add(prime);
	        
	        if ( asc.size() >= maxAscSize ) {
	            if ( asc.size() > maxAscSize ) {
	                maxAscSize = asc.size();
	                maxAsc.clear();
	            }
	            maxAsc.add( new ArrayList<Integer>(asc) );
	        }
	        
	        final int descSize = desc.size();
	        if ( descSize > 1 && prime - desc.get(descSize - 1) >= desc.get(descSize - 1) - desc.get(descSize - 2) ) {
	            desc = new ArrayList<Integer>(desc.subList(descSize - 1, desc.size()));
	        }
	        desc.add(prime);
	        
	        if ( desc.size() >= maxDescSize ) {
	            if ( desc.size() > maxDescSize ) {
	                maxDescSize = desc.size();
	                maxDesc.clear();
	            }
	            maxDesc.add( new ArrayList<Integer>(desc) );
	        }
	    }
	    
	    System.out.println("Longest run(s) of ascending prime gaps up to " + limit + ":");
	    for ( List<Integer> list : maxAsc ) {
	        displayResult(list);
	    }
	    System.out.println();
	    
	    System.out.println("Longest run(s) of descending prime gaps up to " + limit + ":");
	    for( List<Integer> list : maxDesc ) {
	        displayResult(list);
	    }
	}
	
	private static List<Integer> listPrimeNumbers(int aLimit) {
		BitSet sieve = new BitSet(aLimit + 1);
		sieve.set(2, aLimit + 1);
		for ( int i = 2; i <= Math.sqrt(aLimit); i = sieve.nextSetBit(i + 1) ) {
			for ( int j = i * i; j <= aLimit; j = j + i ) {
				sieve.clear(j);
			}
		}
		
		List<Integer> result = new ArrayList<Integer>(sieve.cardinality());
		for ( int i = 2; i >= 0; i = sieve.nextSetBit(i + 1) ) {
			result.add(i);
		}
		return result;
	}
	
	private static void displayResult(List<Integer> aList) {
		for ( int i = 0; i < aList.size(); i++ ) {
	        if ( i > 0 ) {
	            System.out.print(" (" + ( aList.get(i) - aList.get(i - 1) ) + ") ");
	        }
	        System.out.print(aList.get(i));
	    }
	    System.out.println();
	}

}

You may also check:How to resolve the algorithm Memory allocation step by step in the Wren programming language
You may also check:How to resolve the algorithm Loops/Nested step by step in the OCaml programming language
You may also check:How to resolve the algorithm Colorful numbers step by step in the Java programming language
You may also check:How to resolve the algorithm Range consolidation step by step in the Racket programming language
You may also check:How to resolve the algorithm Test a function step by step in the PureBasic programming language