Рубрики

Изначальный ряд

Учитывая число n, задача состоит в том, чтобы вычислить его изначальное значение. Примориал (обозначаемый как P n #) является произведением первых n простых чисел. Изначальное число аналогично факториальному числа. В изначальном не умножаются все натуральные числа, умножаются только простые числа, чтобы вычислить первичное число. Обозначается с помощью P #.

Примеры:

Input: n = 3
Output: 30 
Priomorial = 2 * 3 * 5 = 30
As a side note, factorial is 2 * 3 * 4 * 5

Input: n = 5
Output: 2310
Primorial = 2 * 3 * 5 * 7 * 11 

Наивный подход заключается в проверке всех чисел от 1 до n одно за другим, простое или нет, если да, то сохраните умножение в результате, аналогично сохраните результат умножения простых чисел до n.

Эффективный метод состоит в том, чтобы найти все простые числа, используя сито Сундарама, а затем просто вычислить первородное число, умножив их все.

C ++

// C ++ программа для поиска Примориала заданных чисел
#include<bits/stdc++.h>

using namespace std;

const int MAX = 1000000;

  
// вектор для хранения всех простых чисел, меньших и равных 10 ^ 6

vector <int> primes;

  
// Функция для сита сундарам. Эта функция хранит все
// простые числа меньше MAX в простых числах

void sieveSundaram()

{

    // В общем сито сундарам, производит простые числа меньше

    // чем (2 * x + 2) для числа данного числа x. поскольку

    // мы хотим, чтобы простые числа были меньше, чем MAX, мы уменьшаем MAX до половины

    // Этот массив используется для разделения чисел вида

    // i + j + 2ij от других, где 1 <= i <= j

    bool marked[MAX/2 + 1] = {0};

  

    // Основная логика сундарама. Отметьте все числа, которые

    // не генерируем простое число, выполняя 2 * i + 1

    for (int i = 1; i <= (sqrt(MAX)-1)/2 ; i++)

        for (int j = (i*(i+1))<<1 ; j <= MAX/2 ; j += 2*i +1)

            marked[j] = true;

  

    // Поскольку 2 - простое число

    primes.push_back(2);

  

    // Распечатать другие простые числа. Оставшиеся простые числа

    // форма 2 * i + 1 такая, что отмеченный [i] является ложным.

    for (int i=1; i<=MAX/2; i++)

        if (marked[i] == false)

            primes.push_back(2*i + 1);

}

  
// Функция для вычисления первородства n

int calculatePrimorial(int n)

{

    // Умножаем первые n простых чисел

    int result = 1;  

    for (int i=0; i<n; i++)

       result = result * primes[i];

    return result;

}

  
// Код драйвера

int main()

{

    int n = 5;

    sieveSundaram();

    for (int i = 1 ; i<= n; i++)

        cout << "Primorial(P#) of " << i << " is "

            << calculatePrimorial(i) <<endl;

    return 0;

}

Джава

// Java программа для поиска Примориала заданных чисел

import java.util.*;

  

class GFG{

  

public static int MAX = 1000000;

  
// вектор для хранения всех простых чисел, меньших и равных 10 ^ 6

static ArrayList<Integer> primes = new ArrayList<Integer>();

  
// Функция для сита сундарам. Эта функция хранит все
// простые числа меньше MAX в простых числах

static void sieveSundaram()

{

    // В общем сито сундарам, производит простые числа меньше

    // чем (2 * x + 2) для числа данного числа x. поскольку

    // мы хотим, чтобы простые числа были меньше, чем MAX, мы уменьшаем MAX до половины

    // Этот массив используется для разделения чисел вида

    // i + j + 2ij от других, где 1 <= i <= j

    boolean[] marked = new boolean[MAX];

  

    // Основная логика сундарама. Отметьте все числа, которые

    // не генерируем простое число, выполняя 2 * i + 1

    for (int i = 1; i <= (Math.sqrt(MAX) - 1) / 2 ; i++)

    {

        for (int j = (i * (i + 1)) << 1 ; j <= MAX / 2 ; j += 2 * i + 1)

        {

            marked[j] = true;

        }

    }

  

    // Поскольку 2 - простое число

    primes.add(2);

  

    // Распечатать другие простые числа. Оставшиеся простые числа

    // форма 2 * i + 1 такая, что отмеченный [i] является ложным.

    for (int i = 1; i <= MAX / 2; i++)

    {

        if (marked[i] == false)

        {

            primes.add(2 * i + 1);

        }

    }

}

  
// Функция для вычисления первородства n

static int calculatePrimorial(int n)

{

    // Умножаем первые n простых чисел

    int result = 1;

    for (int i = 0; i < n; i++)

    {

    result = result * primes.get(i);

    }

    return result;

}

  
// Код драйвера

public static void main(String[] args)

{

    int n = 5;

    sieveSundaram();

    for (int i = 1 ; i <= n; i++)

    {

        System.out.println("Primorial(P#) of "+i+" is "+calculatePrimorial(i));

    }

}
}
// Этот код предоставлен Mits

python3

# Python3 программа для поиска Примориала по заданным числам

import math

MAX = 1000000

  
# вектор для хранения всех простых чисел, меньших и равных 10 ^ 6

primes=[]; 

  
# Функция для сита сундарам. Эта функция хранит все
# простые числа меньше MAX в простых числах

def sieveSundaram():

   

    # Вообще сито сундарам, производит простые числа меньше

    # чем (2 * x + 2) для числа данного числа x. поскольку

    # мы хотим, чтобы простые числа были меньше, чем MAX, мы уменьшаем MAX до половины

    # Этот массив используется для разделения чисел вида

    # i + j + 2ij от других, где 1 <= i <= j

    marked=[False]*(int(MAX/2)+1); 

  

    # Основная логика Сундарама. Отметьте все числа, которые

    # не генерировать простое число, выполнив 2 * i + 1

    for i in range(1,int((math.sqrt(MAX)-1)/2)+1): 

        for j in range(((i*(i+1))<<1),(int(MAX/2)+1),(2*i+1)): 

            marked[j] = True

  

    # Так как 2 - простое число

    primes.append(2); 

  

    # Распечатать другие простые числа. Оставшиеся простые числа

    # form 2 * i + 1 такой, что отмеченный [i] является ложным.

    for i in range(1,int(MAX/2)): 

        if (marked[i] == False): 

            primes.append(2*i + 1); 

  
# Функция для расчета прародителя n

def calculatePrimorial(n): 

    # Умножьте первые n простых чисел

    result = 1

    for i in range(n):

        result = result * primes[i]; 

    return result; 

  
# Код драйвера

n = 5

sieveSundaram(); 

for i in range(1,n+1):

    print("Primorial(P#) of",i,"is",calculatePrimorial(i)); 

  
# Этот код предоставлен mits

C #

// C # программа для поиска Примориала заданных чисел

using System; 

using System.Collections;

  

class GFG{

  

public static int MAX = 1000000;

  
// вектор для хранения всех простых чисел, меньших и равных 10 ^ 6

static ArrayList primes = new ArrayList();

  
// Функция для сита сундарам. Эта функция хранит все
// простые числа меньше MAX в простых числах

static void sieveSundaram()

{

    // В общем сито сундарам, производит простые числа меньше

    // чем (2 * x + 2) для числа данного числа x. поскольку

    // мы хотим, чтобы простые числа были меньше, чем MAX, мы уменьшаем MAX до половины

    // Этот массив используется для разделения чисел вида

    // i + j + 2ij от других, где 1 <= i <= j

    bool[] marked = new bool[MAX];

  

    // Основная логика сундарама. Отметьте все числа, которые

    // не генерируем простое число, выполняя 2 * i + 1

    for (int i = 1; i <= (Math.Sqrt(MAX) - 1) / 2 ; i++)

    {

        for (int j = (i * (i + 1)) << 1 ; j <= MAX / 2 ; j += 2 * i + 1)

        {

            marked[j] = true;

        }

    }

  

    // Поскольку 2 - простое число

    primes.Add(2);

  

    // Распечатать другие простые числа. Оставшиеся простые числа

    // форма 2 * i + 1 такая, что отмеченный [i] является ложным.

    for (int i = 1; i <= MAX / 2; i++)

    {

        if (marked[i] == false)

        {

            primes.Add(2 * i + 1);

        }

    }

}

  
// Функция для вычисления первородства n

static int calculatePrimorial(int n)

{

    // Умножаем первые n простых чисел

    int result = 1;

    for (int i = 0; i < n; i++)

    {

    result = result * (int)primes[i];

    }

    return result;

}

  
// Код драйвера

public static void Main()

{

    int n = 5;

    sieveSundaram();

    for (int i = 1 ; i <= n; i++)

    {

        System.Console.WriteLine("Primorial(P#) of "+i+" is "+calculatePrimorial(i));

    }

}
}
// Этот код предоставлен Mits

PHP

<?php
// PHP программа для поиска Приморского
// заданных номеров

$MAX = 100000;

  
// вектор для хранения всех простых чисел
// чем и равен 10 ^ 6

$primes = array();

  
// Функция для сита сундарам.
// Эта функция хранит все простые
// числа меньше MAX в простых числах

function sieveSundaram()

{

    global $MAX, $primes;

      

    // В общем сито сундарам,

    // производит простые числа меньше

    // (2 * x + 2) для заданного числа

    // номер х. Так как мы хотим простые числа

    // меньше, чем MAX, мы уменьшаем MAX

    // до половины. Этот массив используется для

    // отдельные номера формы

    // i + j + 2ij от других, где 1 <= i <= j

    $marked = array_fill(0, $MAX / 2 + 1, 0);

  

    // Основная логика сундарама. Отметьте все числа, которые

    // не генерируем простое число, выполняя 2 * i + 1

    for ($i = 1; $i <= (sqrt($MAX) - 1) / 2 ; $i++)

        for ($j = ($i * ($i + 1)) << 1 ;

             $j <= $MAX / 2 ; $j += 2 * $i + 1)

            $marked[$j] = true;

  

    // Поскольку 2 - простое число

    array_push($primes, 2);

  

    // Распечатать другие простые числа. Оставшиеся простые числа

    // имеют форму 2 * i + 1, такую что

    // отмечено [i] ложно.

    for ($i = 1; $i <= $MAX / 2; $i++)

        if ($marked[$i] == false)

            array_push($primes, (2 * $i + 1));

}

  
// Функция для вычисления первородства n

function calculatePrimorial($n)

{

    global $primes;

      

    // Умножаем первые n простых чисел

    $result = 1; 

    for ($i = 0; $i < $n; $i++)

    $result = $result * $primes[$i];

    return $result;

}

  
// Код драйвера

$n = 5;

sieveSundaram();

for ($i = 1 ; $i<= $n; $i++)

    echo "Primorial(P#) of " . $i

         " is " . calculatePrimorial($i) . "\n";

  
// Этот код предоставлен mits
?>


Выход:

Primorial(P#) of 1 is 2
Primorial(P#) of 2 is 6
Primorial(P#) of 3 is 30
Primorial(P#) of 4 is 210
Primorial(P#) of 5 is 2310

Эта статья предоставлена Сахилом Чхаброй (KILLER) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Изначальный ряд

0.00 (0%) 0 votes