原文:
给定一个整数 n ，任务是打印 n 整数 ≤ 10 9 ，使得这些整数中没有两个连续的是同素的，并且每 3 个连续的是同素的。
示例:
输入:n = 3 t3】输出: 6 15 10
输入:n = 4 t3】输出: 6 15 35 14
进场:
- 我们可以将连续的素数相乘，最后一个数只需乘以 gcd(last，last-1) * 2 。我们这样做是为了使(n–1)第t5】号、第 n号和第 1号也能遵循问题陈述中提到的属性。
- 问题的另一个重要部分是数字应该是 ≤ 10 9 。如果你只是把连续的质数相乘，在 3700 个左右的数字之后，数值会越过 10 9 。所以我们只需要用那些质数，它们的乘积不会越过 10 9 。
- 为了有效地做到这一点，考虑少量的质数，比如前 550 个质数，并以这样一种方式选择它们，使得在制作产品时，没有数字被重复。我们首先连续选择每个素数，然后选择间隔为 2 和 3 的素数，以此类推。通过这样做，我们已经确保没有数字被重复。
所以我们会选择 5，11，17，… 下次我们可以从 7 开始选择， 7，13，19，…
下面是上述方法的实现:
c
// c implementation of the approach
#include
using namespace std;
#define limit 1000000000
#define max_prime 2000000
#define max 1000000
#define i_max 50000
map mp;
int b[max];
int p[max];
int j = 0;
bool prime[max_prime 1];
// function to generate sieve of
// eratosthenes
void sieveoferatosthenes(int n)
{
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p ) {
// if prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
for (int i = p * p; i <= n; i = p)
prime[i] = false;
}
}
// add the prime numbers to the array b
for (int p = 2; p <= n; p ) {
if (prime[p]) {
b[j ] = p;
}
}
}
// function to return the gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// function to print the required
// sequence of integers
void printseries(int n)
{
sieveoferatosthenes(max_prime);
int i, g, k, l, m, d;
int ar[i_max 2];
for (i = 0; i < j; i ) {
if ((b[i] * b[i 1]) > limit)
break;
// including the primes in a series
// of primes which will be later
// multiplied
p[i] = b[i];
// this is done to mark a product
// as existing
mp[b[i] * b[i 1]] = 1;
}
// maximum number of primes that we consider
d = 550;
bool flag = false;
// for different interval
for (k = 2; (k < d - 1) && !flag; k ) {
// for different starting index of jump
for (m = 2; (m < d) && !flag; m ) {
// for storing the numbers
for (l = m k; l < d; l = k) {
// checking for occurrence of a
// product. also checking for the
// same prime occurring consecutively
if (((b[l] * b[l k]) < limit)
&& (l k) < d && p[i - 1] != b[l k]
&& p[i - 1] != b[l] && mp[b[l] * b[l k]] != 1) {
if (mp[p[i - 1] * b[l]] != 1) {
// including the primes in a
// series of primes which will
// be later multiplied
p[i] = b[l];
mp[p[i - 1] * b[l]] = 1;
i ;
}
}
if (i >= i_max) {
flag = true;
break;
}
}
}
}
for (i = 0; i < n; i )
ar[i] = p[i] * p[i 1];
for (i = 0; i < n - 1; i )
cout << ar[i] << " ";
g = gcd(ar[n - 1], ar[n - 2]);
cout << g * 2 << endl;
}
// driver code
int main()
{
int n = 4;
printseries(n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation of the approach
import java.util.*;
class gfg
{
static int limit = 1000000000;
static int max_prime = 2000000;
static int max = 1000000;
static int i_max = 50000;
static hashmap mp = new hashmap();
static int []b = new int[max];
static int []p = new int[max];
static int j = 0;
static boolean []prime = new boolean[max_prime 1];
// function to generate sieve of
// eratosthenes
static void sieveoferatosthenes(int n)
{
for(int i = 0; i < max_prime 1; i )
prime[i] = true;
for (int p = 2; p * p <= n; p )
{
// if prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
for (int i = p * p; i <= n; i = p)
prime[i] = false;
}
}
// add the prime numbers to the array b
for (int p = 2; p <= n; p )
{
if (prime[p])
{
b[j ] = p;
}
}
}
// function to return the gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// function to print the required
// sequence of integers
static void printseries(int n)
{
sieveoferatosthenes(max_prime);
int i, g, k, l, m, d;
int []ar = new int[i_max 2];
for (i = 0; i < j; i )
{
if ((b[i] * b[i 1]) > limit)
break;
// including the primes in a series
// of primes which will be later
// multiplied
p[i] = b[i];
// this is done to mark a product
// as existing
mp.put(b[i] * b[i 1], 1);
}
// maximum number of primes that we consider
d = 550;
boolean flag = false;
// for different interval
for (k = 2; (k < d - 1) && !flag; k )
{
// for different starting index of jump
for (m = 2; (m < d) && !flag; m )
{
// for storing the numbers
for (l = m k; l < d; l = k)
{
// checking for occurrence of a
// product. also checking for the
// same prime occurring consecutively
if (((b[l] * b[l k]) < limit) &&
mp.containskey(b[l] * b[l k]) &&
mp.containskey(p[i - 1] * b[l]) &&
(l k) < d && p[i - 1] != b[l k] &&
p[i - 1] != b[l] &&
mp.get(b[l] * b[l k]) != 1)
{
if (mp.get(p[i - 1] * b[l]) != 1)
{
// including the primes in a
// series of primes which will
// be later multiplied
p[i] = b[l];
mp.put(p[i - 1] * b[l], 1);
i ;
}
}
if (i >= i_max)
{
flag = true;
break;
}
}
}
}
for (i = 0; i < n; i )
ar[i] = p[i] * p[i 1];
for (i = 0; i < n - 1; i )
system.out.print(ar[i] " ");
g = gcd(ar[n - 1], ar[n - 2]);
system.out.print(g * 2);
}
// driver code
public static void main(string[] args)
{
int n = 4;
printseries(n);
}
}
// this code is contributed by 29ajaykumar
python 3
# python3 implementation of
# the above approach
limit = 1000000000
max_prime = 2000000
max = 1000000
i_max = 50000
mp = {}
b = [0] * max
p = [0] * max
j = 0
prime = [true] * (max_prime 1)
# function to generate sieve of
# eratosthenes
def sieveoferatosthenes(n):
global j
p = 2
while p * p <= n:
# if prime[p] is not changed,
# then it is a prime
if (prime[p] == true):
for i in range(p * p, n 1, p):
prime[i] = false
p = 1
# add the prime numbers to the array b
for p in range(2, n 1):
if (prime[p]):
b[j] = p
j = 1
# function to return
# the gcd of a and b
def gcd(a, b):
if (b == 0):
return a
return gcd(b, a % b)
# function to print the required
# sequence of integers
def printseries(n):
sieveoferatosthenes(max_prime)
ar = [0] * (i_max 2)
for i in range(j):
if ((b[i] * b[i 1]) > limit):
break
# including the primes in a series
# of primes which will be later
# multiplied
p[i] = b[i]
# this is done to mark a product
# as existing
mp[b[i] * b[i 1]] = 1
# maximum number of
# primes that we consider
d = 550
flag = false
# for different interval
k = 2
while (k < d - 1) and not flag:
# for different starting
# index of jump
m = 2
while (m < d) and not flag:
# for storing the numbers
for l in range(m k, d, k):
# checking for occurrence of a
# product. also checking for the
# same prime occurring consecutively
if (((b[l] * b[l k]) < limit) and
(l k) < d and p[i - 1] != b[l k] and
p[i - 1] != b[l] and
((b[l] * b[l k] in mp) and
mp[b[l] * b[l k]] != 1)):
if (mp[p[i - 1] * b[l]] != 1):
# including the primes in a
# series of primes which will
# be later multiplied
p[i] = b[l]
mp[p[i - 1] * b[l]] = 1
i = 1
if (i >= i_max):
flag = true
break
m = 1
k = 1
for i in range(n):
ar[i] = p[i] * p[i 1]
for i in range(n - 1):
print(ar[i], end = " ")
g = gcd(ar[n - 1], ar[n - 2])
print(g * 2)
# driver code
if __name__ == "__main__":
n = 4
printseries(n)
# this code is contributed by chitranayal
c
// c# implementation of the approach
using system;
using system.collections.generic;
class gfg
{
static int limit = 1000000000;
static int max_prime = 2000000;
static int max = 1000000;
static int i_max = 50000;
static dictionary mp = new dictionary();
static int []b = new int[max];
static int []p = new int[max];
static int j = 0;
static bool []prime = new bool[max_prime 1];
// function to generate sieve of
// eratosthenes
static void sieveoferatosthenes(int n)
{
for(int i = 0; i < max_prime 1; i )
prime[i] = true;
for (int p = 2; p * p <= n; p )
{
// if prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
for (int i = p * p; i <= n; i = p)
prime[i] = false;
}
}
// add the prime numbers to the array b
for (int p = 2; p <= n; p )
{
if (prime[p])
{
b[j ] = p;
}
}
}
// function to return the gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// function to print the required
// sequence of integers
static void printseries(int n)
{
sieveoferatosthenes(max_prime);
int i, g, k, l, m, d;
int []ar = new int[i_max 2];
for (i = 0; i < j; i )
{
if ((b[i] * b[i 1]) > limit)
break;
// including the primes in a series
// of primes which will be later
// multiplied
p[i] = b[i];
// this is done to mark a product
// as existing
mp.add(b[i] * b[i 1], 1);
}
// maximum number of primes that we consider
d = 550;
bool flag = false;
// for different interval
for (k = 2; (k < d - 1) && !flag; k )
{
// for different starting index of jump
for (m = 2; (m < d) && !flag; m )
{
// for storing the numbers
for (l = m k; l < d; l = k)
{
// checking for occurrence of a
// product. also checking for the
// same prime occurring consecutively
if (((b[l] * b[l k]) < limit) &&
mp.containskey(b[l] * b[l k]) &&
mp.containskey(p[i - 1] * b[l]) &&
(l k) < d && p[i - 1] != b[l k] &&
p[i - 1] != b[l] &&
mp[b[l] * b[l k]] != 1)
{
if (mp[p[i - 1] * b[l]] != 1)
{
// including the primes in a
// series of primes which will
// be later multiplied
p[i] = b[l];
mp.add(p[i - 1] * b[l], 1);
i ;
}
}
if (i >= i_max)
{
flag = true;
break;
}
}
}
}
for (i = 0; i < n; i )
ar[i] = p[i] * p[i 1];
for (i = 0; i < n - 1; i )
console.write(ar[i] " ");
g = gcd(ar[n - 1], ar[n - 2]);
console.write(g * 2);
}
// driver code
public static void main(string[] args)
{
int n = 4;
printseries(n);
}
}
// this code is contributed by 29ajaykumar
java 描述语言
output:
6 15 35 14
13 * 6, 17 * 15, 19 * 10, 23 * 6, 29 * 15, ........upto n - 2 terms.
(n - 1)th term = (n - 1)th prime * 7.
nth term = 7 * 11.
again, first term = first term * 11 to make 1st and last noncoprime.
for example, n = 5
6 * 11 * 13, 15 * 17, 10 * 19, 11 * 19, 7 * 11
现在我们看到，我们不能使用列表中的 7 和 11，因为它们用于生成最后一项和第二项。 下面是上述方法的实现:
c
// c implementation of the approach
#include
using namespace std;
const int max = 620000;
int prime[max];
// function for sieve of eratosthenes
void sieve()
{
for (int i = 2; i < max; i ) {
if (prime[i] == 0) {
for (int j = 2 * i; j < max; j = i) {
prime[j] = 1;
}
}
}
}
// function to print the required sequence
void printsequence(int n)
{
sieve();
vector v, u;
// store only the required primes
for (int i = 13; i < max; i ) {
if (prime[i] == 0) {
v.push_back(i);
}
}
// base condition
if (n == 3) {
cout << 6 << " " << 10 << " " << 15;
return;
}
int k;
for (k = 0; k < n - 2; k ) {
// first integer in the list
if (k % 3 == 0) {
u.push_back(v[k] * 6);
}
// second integer in the list
else if (k % 3 == 1) {
u.push_back(v[k] * 15);
}
// third integer in the list
else {
u.push_back(v[k] * 10);
}
}
k--;
// generate (n - 1)th term
u.push_back(v[k] * 7);
// generate nth term
u.push_back(7 * 11);
// modify first term
u[0] = u[0] * 11;
// print the sequence
for (int i = 0; i < u.size(); i ) {
cout << u[i] << " ";
}
}
// driver code
int main()
{
int n = 4;
printsequence(n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation of the approach
import java.util.*;
class gfg
{
static int max = 620000;
static int[] prime = new int[max];
// function for sieve of eratosthenes
static void sieve()
{
for (int i = 2; i < max; i )
{
if (prime[i] == 0)
{
for (int j = 2 * i;
j < max; j = i)
{
prime[j] = 1;
}
}
}
}
// function to print the required sequence
static void printsequence(int n)
{
sieve();
vector v = new vector();
vector u = new vector();
// store only the required primes
for (int i = 13; i < max; i )
{
if (prime[i] == 0)
{
v.add(i);
}
}
// base condition
if (n == 3)
{
system.out.print(6 " " 10 " " 15);
return;
}
int k;
for (k = 0; k < n - 2; k )
{
// first integer in the list
if (k % 3 == 0)
{
u.add(v.get(k) * 6);
}
// second integer in the list
else if (k % 3 == 1)
{
u.add(v.get(k) * 15);
}
// third integer in the list
else
{
u.add(v.get(k) * 10);
}
}
k--;
// generate (n - 1)th term
u.add(v.get(k) * 7);
// generate nth term
u.add(7 * 11);
// modify first term
u.set(0, u.get(0) * 11);
// print the sequence
for (int i = 0; i < u.size(); i )
{
system.out.print(u.get(i) " ");
}
}
// driver code
public static void main(string[] args)
{
int n = 4;
printsequence(n);
}
}
// this code is contributed by rajput-ji
python 3
# python3 program for the above approach
max = 620000
prime = [0] * max
# function for sieve of eratosthenes
def sieve():
for i in range(2, max):
if (prime[i] == 0):
for j in range(2 * i, max, i):
prime[j] = 1
# function to print the required sequence
def printsequence (n):
sieve()
v = []
u = []
# store only the required primes
for i in range(13, max):
if (prime[i] == 0):
v.append(i)
# base condition
if (n == 3):
print(6, 10, 15)
return
k = 0
for k in range(n - 2):
# first integer in the list
if (k % 3 == 0):
u.append(v[k] * 6)
# second integer in the list
elif (k % 3 == 1):
u.append(v[k] * 15)
# third integer in the list
else:
u.append(v[k] * 10)
# generate (n - 1)th term
u.append(v[k] * 7)
# generate nth term
u.append(7 * 11)
# modify first term
u[0] = u[0] * 11
# print the sequence
print(*u)
# driver code
if __name__ == '__main__':
n = 4
printsequence(n)
# this code is contributed by himanshu77
c
// c# implementation of the approach
using system;
using system.collections.generic;
class gfg
{
static int max = 620000;
static int[] prime = new int[max];
// function for sieve of eratosthenes
static void sieve()
{
for (int i = 2; i < max; i )
{
if (prime[i] == 0)
{
for (int j = 2 * i;
j < max; j = i)
{
prime[j] = 1;
}
}
}
}
// function to print the required sequence
static void printsequence(int n)
{
sieve();
list v = new list();
list u = new list();
// store only the required primes
for (int i = 13; i < max; i )
{
if (prime[i] == 0)
{
v.add(i);
}
}
// base condition
if (n == 3)
{
console.write(6 " " 10 " " 15);
return;
}
int k;
for (k = 0; k < n - 2; k )
{
// first integer in the list
if (k % 3 == 0)
{
u.add(v[k] * 6);
}
// second integer in the list
else if (k % 3 == 1)
{
u.add(v[k] * 15);
}
// third integer in the list
else
{
u.add(v[k] * 10);
}
}
k--;
// generate (n - 1)th term
u.add(v[k] * 7);
// generate nth term
u.add(7 * 11);
// modify first term
u[0] = u[0] * 11;
// print the sequence
for (int i = 0; i < u.count; i )
{
console.write(u[i] " ");
}
}
// driver code
public static void main(string[] args)
{
int n = 4;
printsequence(n);
}
}
// this code is contributed by princi singh
java 描述语言
output:
858 255 119 77
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
