Almost prime numbers on Julia

This example demonstrates the implementation of the algorithm for searching for "almost prime numbers"

Introduction

The almost prime numbers algorithm is used to find natural numbers that have a given number of prime factors, taking into account multiplicity. These numbers find applications in number theory, cryptography, and other areas of mathematics.

What are "almost prime numbers"?

An almost prime number of the order (k-almost prime) is a natural number that has exactly prime factors, counting multiplicities. For example:

1-almost primes (primes): 2, 3, 5, 7, 11...
2- almost primes (semisimple numbers): 4, 6, 9, 10, 14...
3- almost primes: 8, 12, 18, 20, 27...

The main part

Before using the external Primes package, you must install it.:

import Pkg; Pkg.add("Primes")

We connect the necessary package for working with prime numbers:

using Primes  # A package for working with prime numbers and factorization

We define a function to check whether a number is almost prime.:

# The function checks whether the number n is almost prime of order k
# almost prime of the kth order is a number with exactly k prime factors (taking into account multiplicity)

isalmostprime(n::Integer, k::Integer) = sum(values(factor(n))) == k

isalmostprime (generic function with 1 method)

factor(n) - returns a dictionary of prime factors and their powers

values(factor(n)) - extracts the powers of prime factors

sum(values(factor(n))) - sum of all powers = total number of prime factors, taking into account multiplicity

We implement the main function to generate the first almost prime numbers of the order :

# The function returns the first N almost-k-primes
function almostprimes(N::Integer, k::Integer) 
    # Creating a vector for storing results of size N of type k
    P = Vector{typeof(k)}(undef,N)
    # Initialize the counter of found numbers and the current checked number
    i = 0; n = 2
    # The cycle continues until we find N numbers
    while i < N
        # If the current number is almost prime on the order of k
        if isalmostprime(n, k) 
            # We save it to the results array and increment the counter.
            P[i += 1] = n 
        end
        # Moving on to the next number
        n += 1
    end
    # We return the vector of found almost prime numbers
    return P
end

almostprimes (generic function with 1 method)

We generate and output the first 10 almost prime numbers for each order from 1 to 5:

# For each value of k from 1 to 5, we generate and output the first 10 almost prime numbers
for k in 1:5
    # We generate the first 10 almost prime numbers of the order k
    primes_k = almostprimes(10, k)
    # Convert numbers to strings and connect them with commas
    result_str = join(primes_k, ", ")
    # We output the result in formatted form
    println("$k-almost prime: $result_str...")
end

1-почти простые: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...
2-почти простые: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26...
3-почти простые: 8, 12, 18, 20, 27, 28, 30, 42, 44, 45...
4-почти простые: 16, 24, 36, 40, 54, 56, 60, 81, 84, 88...
5-почти простые: 32, 48, 72, 80, 108, 112, 120, 162, 168, 176...

How the function works `factor`?

To understand how the algorithm works, it is important to know that the function factor(n) from the package Primes returns a dictionary where the keys are the prime factors of a number, and the values are their powers. For example:

factor(12) it will return Dict(2 => 2, 3 => 1) because
sum(values(Dict(2 => 2, 3 => 1))) = 2 + 1 = 3, which corresponds to three prime factors: 2, 2, 3

Conclusion

We have reviewed the implementation of the algorithm for searching for almost prime numbers in the Julia language. The program allows you to generate almost prime numbers of various orders, which can be useful for research in number theory and other mathematical applications. Using the Primes package has greatly simplified the implementation of number factorization.

The example was developed using materials from Rosetta Code