Dado un rango [L, R]. La tarea es encontrar el producto de todos los números primos en el rango dado de L a R ambos inclusive módulo 10^9 + 7.
Ejemplos:
Input: L = 10, R = 20 Output: 46189 Prime numbers between [10, 20] are: 11, 13, 17, 19 Therefore, product = 11 * 13 * 17 * 19 = 46189 Input: L = 15, R = 25 Output: 7429
Una solución simple es atravesar de L a R, verificar si el número actual es primo. Si es así, multiplícalo por el producto. Finalmente, imprima el producto.
Una solución eficiente es usar la criba de Eratóstenes para encontrar todos los números primos hasta un límite determinado. Luego, calcule una array de productos de prefijo para almacenar el producto hasta cada valor antes del límite. Una vez que tenemos la array de prefijos, solo tenemos que devolver (prefijo [R] *modular_inverse (prefijo [L-1]))% (10 ^ 9 + 7).
Nota: el prefijo[i] almacenará el producto de todos los números primos del 1 al i.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find product of primes
// in range L to R
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
const int MAX = 10000;
// prefix[i] is going to store product of primes
// till i (including i).
int prefix[MAX + 1];
// Function to build the prefix product array
void buildPrefix()
{
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
bool prime[MAX + 1];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
// Build prefix array
prefix[0] = prefix[1] = 1;
for (int p = 2; p <= MAX; p++) {
prefix[p] = prefix[p - 1];
if (prime[p])
prefix[p] = (prefix[p] * p) % mod;
}
}
/* Iterative Function to calculate (x^y)%p in O(log y) */
long long int power(long long int x, long long int y, int p)
{
// Initialize result
long long int res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
// y = y/2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Returns modular inverse
long long int inverse(long long int n)
{
return power(n, mod - 2, mod);
}
// Function to return product of prime in range
long long int productPrimeRange(int L, int R)
{
return (prefix[R] * inverse(prefix[L - 1])) % mod;
}
// Driver code
int main()
{
buildPrefix();
int L = 10, R = 20;
cout << productPrimeRange(L, R) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find product of primes
// in range L to R
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#define mod 1000000007
const int MAX = 10000;
// Function to build the prefix product array
void buildPrefix(int prefix[])
{
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
bool prime[MAX + 1];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
// Build prefix array
prefix[0] = prefix[1] = 1;
for (int p = 2; p <= MAX; p++) {
prefix[p] = prefix[p - 1];
if (prime[p])
prefix[p] = (prefix[p] * p) % mod;
}
}
/* Iterative Function to calculate (x^y)%p in O(log y) */
long long int power(long long int x, long long int y, int p)
{
// Initialize result
long long int res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
// y = y/2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Returns modular inverse
long long int inverse(long long int n)
{
return power(n, mod - 2, mod);
}
// Function to return product of prime in range
long long int productPrimeRange(int L, int R, int prefix[])
{
return (prefix[R] * inverse(prefix[L - 1])) % mod;
}
// Driver code
int main()
{
int prefix[MAX + 1];
buildPrefix(prefix);
int L = 10, R = 20;
printf("%lld", productPrimeRange(L, R, prefix));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find product of primes
// in range L to R
import java.io.*;
class GFG {
static int mod = 1000000007;
static int MAX = 10000;
// prefix[i] is going to store product of primes
// till i (including i).
static int[] prefix = new int[MAX + 1];
// Function to build the prefix product array
static void buildPrefix()
{
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
boolean prime[] = new boolean[MAX + 1];
for (int i = 0; i < MAX + 1; i++)
prime[i] = true;
// memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
// Build prefix array
prefix[0] = prefix[1] = 1;
for (int p = 2; p <= MAX; p++) {
prefix[p] = prefix[p - 1];
if (prime[p])
prefix[p] = (prefix[p] * p) % mod;
}
}
// Iterative Function to calculate (x^y)%p in O(log y)
static long power(long x, long y, int p)
{
// Initialize result
long res = 1;
// Update x if it is more than or equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now y = y/2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Returns modular inverse
static long inverse(long n)
{
return power(n, mod - 2, mod);
}
// Function to return product of prime in range
static long productPrimeRange(int L, int R)
{
return (prefix[R] * inverse(prefix[L - 1])) % mod;
}
// Driver code
public static void main(String[] args)
{
buildPrefix();
int L = 10, R = 20;
System.out.println(productPrimeRange(L, R));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python 3
# Python 3 program to find product of primes # in range L to R mod = 1000000007 MAX = 10000 # prefix[i] is going to store product of primes # till i (including i). prefix = [0]*(MAX + 1) # Function to build the prefix product array def buildPrefix(): # Create a boolean array "prime[0..n]". A # value in prime[i] will finally be false # if i is Not a prime, else true. prime = [True]*(MAX + 1) p = 2 while p * p <= MAX : # If prime[p] is not changed, then # it is a prime if (prime[p] == True) : # Update all multiples of p for i in range( p * 2, MAX+1, p): prime[i] = False p += 1 # Build prefix array prefix[0] = prefix[1] = 1 for p in range(2,MAX+1) : prefix[p] = prefix[p - 1] if (prime[p]): prefix[p] = (prefix[p] * p) % mod # Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y,p): # Initialize result res = 1 # Update x if it is more than or # equal to p x = x % p while (y > 0) : # If y is odd, multiply x with result if (y & 1): res = (res * x) % p # y must be even now # y = y//2 y = y >> 1 x = (x * x) % p return res # Returns modular inverse def inverse( n): return power(n, mod - 2, mod) # Function to return product of prime in range def productPrimeRange(L, R): return (prefix[R] * inverse(prefix[L - 1])) % mod # Driver code if __name__ == "__main__": buildPrefix() L = 10 R = 20 print(productPrimeRange(L, R)) # this code is contributed by # ChitraNayal
C#
// C# program to find product of
// primes in range L to R
using System;
class GFG
{
static int mod = 1000000007;
static int MAX = 10000;
// prefix[i] is going to store product
// of primes till i (including i).
static int []prefix = new int[MAX + 1];
// Function to build the prefix
// product array
static void buildPrefix()
{
// Create a boolean array "prime[0..n]".
// A value in prime[i] will finally be
// false if i is Not a prime, else true.
bool []prime = new bool[MAX + 1];
for(int i = 0; i < MAX + 1; i++)
prime[i] = true;
//memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= MAX; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
// Build prefix array
prefix[0] = prefix[1] = 1;
for (int p = 2; p <= MAX; p++)
{
prefix[p] = prefix[p - 1];
if (prime[p])
prefix[p] = (prefix[p] * p) % mod;
}
}
/* Iterative Function to calculate
(x^y)%p in O(log y) */
static long power(long x, long y, int p)
{
// Initialize result
long res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply x
// with result
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
// y = y/2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Returns modular inverse
static long inverse(long n)
{
return power(n, mod - 2, mod);
}
// Function to return product
// of prime in range
static long productPrimeRange(int L, int R)
{
return (prefix[R] *
inverse(prefix[L - 1])) % mod;
}
// Driver code
public static void Main ()
{
buildPrefix();
int L = 10, R = 20;
Console.WriteLine(productPrimeRange(L, R));
}
}
// This code is contributed by anuj_67
Javascript
<script>
// Javascript program to find product of primes
// in range L to R
var mod = 100000007
var MAX = 10000;
// prefix[i] is going to store product of primes
// till i (including i).
var prefix = Array(MAX+1);
// Function to build the prefix product array
function buildPrefix()
{
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
var prime = Array(MAX+1).fill(true);
for (var p = 2; p * p <= MAX; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (var i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
// Build prefix array
prefix[0] = prefix[1] = 1;
for (var p = 2; p <= MAX; p++) {
prefix[p] = prefix[p - 1];
if (prime[p])
prefix[p] = (prefix[p] * p) % mod;
}
}
/* Iterative Function to calculate (x^y)%p in O(log y) */
function power(x, y, p)
{
// Initialize result
var res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
// y = y/2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Returns modular inverse
function inverse( n)
{
return power(n, mod - 2, mod);
}
// Function to return product of prime in range
function productPrimeRange(L, R)
{
return (prefix[R] * inverse(prefix[L - 1])) % mod;
}
// Driver code
buildPrefix();
var L = 10, R = 20;
document.write( productPrimeRange(L, R));
</script>
Producción:
46189
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA