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  # Пакет для работы с простыми числами и факторизацией

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

# Функция проверяет, является ли число n почти простым порядка k
# almost prime k-го порядка - число с ровно k простыми множителями (с учетом кратности)

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 :

# Функция возвращает первые N почти-k-простых чисел
function almostprimes(N::Integer, k::Integer) 
    # Создаем вектор для хранения результатов размером N типа k
    P = Vector{typeof(k)}(undef,N)
    # Инициализируем счетчик найденных чисел и текущее проверяемое число
    i = 0; n = 2
    # Цикл продолжается пока не найдем N чисел
    while i < N
        # Если текущее число является почти простыми порядка k
        if isalmostprime(n, k) 
            # Сохраняем его в массив результатов и увеличиваем счетчик
            P[i += 1] = n 
        end
        # Переходим к следующему числу
        n += 1
    end
    # Возвращаем вектор найденных почти простых чисел
    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:

# Для каждого значения k от 1 до 5 генерируем и выводим первые 10 почти простых чисел
for k in 1:5
    # Генерируем первые 10 почти простых чисел порядка k
    primes_k = almostprimes(10, k)
    # Преобразуем числа в строки и соединяем их запятыми
    result_str = join(primes_k, ", ")
    # Выводим результат в форматированном виде
    println("$k-почти простые: $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