How to resolve the algorithm Sequence of primes by trial division step by step in the Julia programming language

Published on 22 June 2024 08:30 PM

How to resolve the algorithm Sequence of primes by trial division step by step in the Julia programming language

Table of Contents

Problem Statement

Generate a sequence of primes by means of trial division.

Trial division is an algorithm where a candidate number is tested for being a prime by trying to divide it by other numbers. You may use primes, or any numbers of your choosing, as long as the result is indeed a sequence of primes. The sequence may be bounded (i.e. up to some limit), unbounded, starting from the start (i.e. 2) or above some given value. Organize your function as you wish, in particular, it might resemble a filtering operation, or a sieving operation. If you want to use a ready-made is_prime function, use one from the Primality by trial division page (i.e., add yours there if it isn't there already).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sequence of primes by trial division step by step in the Julia programming language

The provided Julia code defines a custom Julia struct TDPrimes designed to generate prime numbers up to a specified limit. Here's how this code works:

  1. TDPrimes Struct:

    • The TDPrimes struct is defined as a parametric type with one parameter, T, which must be a subtype of Integer.
    • It has a single field named uplim that specifies the upper limit up to which prime numbers should be generated.
  2. Starting the Prime Number Generator:

    • The start function for the TDPrimes struct initializes the generation of prime numbers by returning the first prime number, 2, as a one-element vector of type T.
  3. Checking if Generation is Done:

    • The done function checks if the generation of prime numbers is complete. It returns true if the last element of the input vector p is greater than the uplim field of the pl struct, indicating that no more primes below uplim remain.
  4. Generating the Next Prime Number:

    • The next function generates the next prime number and updates the input vector p accordingly.
    • It initializes pr to the last element of p (the current prime) and increments npr until it finds the next prime number.
    • The npr value is checked against all the elements in p using the % (modulo) operator to ensure that it is not divisible by any of the previously found prime numbers. This check verifies that npr is a prime number.
    • Once a prime number npr is found, it is appended to p, and the current prime pr is returned as the second output of the function.
  5. Printing Prime Numbers:

    • Outside the TDPrimes struct definition, the code generates prime numbers up to 100 by creating an instance of TDPrimes(100) and iterating over its values.
    • The prime numbers are collected in a vector and then joined together with commas to create a string representation.
    • The resulting string is printed to the console, displaying the prime numbers less than or equal to 100.

In summary, this code provides an efficient way to generate prime numbers up to a specified limit using a custom Julia struct, TDPrimes. The start, done, and next functions work together to incrementally find and store prime numbers in a vector until the desired limit is reached.

Source code in the julia programming language

struct TDPrimes{T<:Integer}
    uplim::T
end

Base.start{T<:Integer}(pl::TDPrimes{T}) = 2ones(T, 1)
Base.done{T<:Integer}(pl::TDPrimes{T}, p::Vector{T}) = p[end] > pl.uplim
function Base.next{T<:Integer}(pl::TDPrimes{T}, p::Vector{T})
    pr = npr = p[end]
    ispr = false
    while !ispr
        npr += 1
        ispr = all(npr % d != 0 for d in p)
    end
    push!(p, npr)
    return pr, p
end

println("Primes ≤ 100: ", join((p for p in TDPrimes(100)), ", "))


  

You may also check:How to resolve the algorithm Check Machin-like formulas step by step in the Julia programming language
You may also check:How to resolve the algorithm Real constants and functions step by step in the Elm programming language
You may also check:How to resolve the algorithm Pseudo-random numbers/PCG32 step by step in the uBasic/4tH programming language
You may also check:How to resolve the algorithm Narcissistic decimal number step by step in the Factor programming language
You may also check:How to resolve the algorithm Department numbers step by step in the Objeck programming language