求助

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int  f(int t)
   
4. {
   
5.         int flag=1;
   
6.         for(int i=2;i<=sqrt(t);i++)
   
7.         {
   
8.                 if(t%i==0)
   
9.                 {
   
10.                         flag=0;
    
11.                         break;
    
12.                 }
    
13.                 else flag=1;
    
14. 
    
15.         }
    
16.         return flag;
    
17. }
    
18. int main()
    
19. {
    
20.     int n,res =0;;
    
21.     cin>>n;
    
22.         vector<int>a;
    
23.     vector<vector<int>>b;
    
24.     for(int i=1;i<=n;i++)a.push_back(i);
    
25.     do{
    
26.         b.push_back(a);
    
27.     }while(next_permutation(a.begin(),a.end()));
    
28.     for(int i=0;i<b.size();i++)
    
29.     {
    
30.         for(int j=0;j<b[i].size()-1;j++)
    
31.         {
    
32.                         if(!f(b[i][j]+b[i][j+1]))
    
33.                         {
    
34.                                 res++;
    
35.                         }
    
36.             
    
37.         }
    
38.                
    
39.     }
    
40.         cout<<res<<endl;
    
41. }

复制代码

题目要求：游游想知道，有多少个长度为nn的排列满足任意两个相邻元素之和都不是素数。你能帮帮她吗？
我们定义，长度为nn的排列值一个长度为nn的数组，其中1到nn每个元素恰好出现了一次。
为什么我这样写不对呢

isdkz

你的代码有一个问题，即你的函数f(t)只判断了t是否为素数，但题目要求的是判断相邻元素之和是否为素数。所以你需要修改你的代码逻辑。

你可以在计算相邻元素之和时，调用函数f()来判断是否为素数。如果相邻元素之和不是素数，则增加计数器res的值。

修改后的代码如下：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. bool isPrime(int num) {
   
5.     if (num <= 1) {
   
6.         return false;
   
7.     }
   
8.     for (int i = 2; i * i <= num; i++) {
   
9.         if (num % i == 0) {
   
10.             return false;
    
11.         }
    
12.     }
    
13.     return true;
    
14. }
    
15. 
    
16. int main() {
    
17.     int n, res = 0;
    
18.     cin >> n;
    
19.     vector<int> a(n);
    
20.     for (int i = 0; i < n; i++) {
    
21.         a[ i] = i + 1;
    
22.     }
    
23.     do {
    
24.         bool flag = true;
    
25.         for (int i = 0; i < n - 1; i++) {
    
26.             if (isPrime(a[ i] + a[i + 1])) {
    
27.                 flag = false;
    
28.                 break;
    
29.             }
    
30.         }
    
31.         if (flag) {
    
32.             res++;
    
33.         }
    
34.     } while (next_permutation(a.begin(), a.end()));
    
35.     cout << res << endl;
    
36.     return 0;
    
37. }
    

复制代码

这样修改后的代码会正确计算满足条件的排列个数。