给定一个整数 n ，任务是找到从范围【1，n】共质数到给定数 n 的所有数的乘积。
示例:
输入: n = 5 输出: 24 说明: 与 5 同素的数字为{1，2，3，4}。 因此，乘积由 1 * 2 * 3 * 4 = 24 给出。
输入: n = 6 输出: 5 说明: 与 6 同素的数字为{1，5}。 因此，要求的乘积等于 1 * 5 = 5
方法:思路是在【1，n】范围内迭代，对于每个数字，检查其带有 n 的 gcd 是否等于 1 。如果发现任何一个数字都是真的，那么就把这个数字包含在结果中。 按照以下步骤解决问题:
- 将产品初始化为 1 。
- 迭代范围【1，n】，如果 i 和 n 的 gcd 为 1 ，则将乘积乘以 i 。
- 完成上述步骤后，打印产品的数值。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
// function to return gcd of a and b
int gcd(int a, int b)
{
// base case
if (a == 0)
return b;
// recursive gcd
return gcd(b % a, a);
}
// function to find the product of
// all the numbers till n that are
// relatively prime to n
int findproduct(unsigned int n)
{
// stores the resultant product
unsigned int result = 1;
// iterate over [2, n]
for (int i = 2; i < n; i ) {
// if gcd is 1, then find the
// product with result
if (gcd(i, n) == 1) {
result *= i;
}
}
// return the final product
return result;
}
// driver code
int main()
{
int n = 5;
cout << findproduct(n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for the
// above approach
import java.util.*;
class gfg{
// function to return
// gcd of a and b
static int gcd(int a, int b)
{
// base case
if (a == 0)
return b;
// recursive gcd
return gcd(b % a, a);
}
// function to find the
// product of all the
// numbers till n that are
// relatively prime to n
static int findproduct(int n)
{
// stores the resultant
// product
int result = 1;
// iterate over [2, n]
for (int i = 2; i < n; i )
{
// if gcd is 1, then
// find the product
// with result
if (gcd(i, n) == 1)
{
result *= i;
}
}
// return the final
// product
return result;
}
// driver code
public static void main(string[] args)
{
int n = 5;
system.out.print(findproduct(n));
}
}
// this code is contributed by rajput-ji
python 3
# python3 program for the
# above approach
# function to return
# gcd of a and b
def gcd(a, b):
# base case
if (a == 0):
return b;
# recursive gcd
return gcd(b % a, a);
# function to find the
# product of all the
# numbers till n that are
# relatively prime to n
def findproduct(n):
# stores the resultant
# product
result = 1;
# iterate over [2, n]
for i in range(2, n):
# if gcd is 1, then
# find the product
# with result
if (gcd(i, n) == 1):
result *= i;
# return the final
# product
return result;
# driver code
if __name__ == '__main__':
n = 5;
print(findproduct(n));
# this code is contributed by 29ajaykumar
c
// c# program for the
// above approach
using system;
class gfg{
// function to return
// gcd of a and b
static int gcd(int a, int b)
{
// base case
if (a == 0)
return b;
// recursive gcd
return gcd(b % a, a);
}
// function to find the
// product of all the
// numbers till n that are
// relatively prime to n
static int findproduct(int n)
{
// stores the resultant
// product
int result = 1;
// iterate over [2, n]
for(int i = 2; i < n; i )
{
// if gcd is 1, then
// find the product
// with result
if (gcd(i, n) == 1)
{
result *= i;
}
}
// return the readonly
// product
return result;
}
// driver code
public static void main(string[] args)
{
int n = 5;
console.write(findproduct(n));
}
}
// this code is contributed by amit katiyar
java 描述语言
output
24
时间复杂度: o(n log n) 辅助空间: o(1)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
