【题目描述】

$n=4$, $=3$, $4$个整数分别为3$,7,12,19$时,可得全部的组合与它们的和为:

3+7+12=22　　 3+7+19=29　　 7+12+19=38　 3+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:(3+7+19=29)。

【输入描述】

        第二行为n个数$x_1{x}_2\dots \dots x_n(1\le x_i\le 5000000)$,各数之间用一个空格隔开)

【输出描述】

        一个整数（满足所有条件的种数）

【样例输入】

4 3   3 7 12 19

【样例输出】

1

山东普及组分数线55

小学组43

首先：

  常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)

时间复杂度可以简单理解为最多执行次数。

一、O(1)

一般情况下没有其他循环和递归调用，时间复杂度一般都是O(1)。比如下面这样的代码

#include<iostream>  using namespace std;  int main(){  	int a=0,b=0,x=0,y=0;  	cin>>a>>b;  	x=a+b;  	y=a-b;  	if(x>y){  	 cout<<x;  	}else{  	 cout<<y;  	}  	return 0;  }

二、O(n)

一般情况下，一个循环的时间复杂度是O(n)，多个循环并列也是取循环次数最多的那个作为时间复杂度。当数据量增大n倍，耗时增大n倍。

#include<iostream>  using namespace std;  int main(){  	int a=n;  	cin>>n;  	for(int i=0;i<n;i++){  	    cout<<i;  	}  	return 0;  }

三、O(n2)、O(n*m)

双重循环嵌套一般就是O(n2)。当数据量增大n倍，耗时增大n方倍。

#include<iostream>  using namespace std;  int main(){  	int n=0;  	cin>>n;  	for(int i=0;i<n;i++){  	    for(int j=0;j<n;j++){  	        cout<<i;  	    }  	}  	return 0;  }

如果循环嵌套外层循环是n，内层循环是m。

#include<iostream>  using namespace std;  int main(){  	int n=0,m=0;  	cin>>n>>m;  	for(int i=0;i<n;i++){  	    for(int j=0;j<m;j++){  	        cout<<i;  	    }  	}  	return 0;  }

这个时候的时间复杂度是O(n*m)。

四、O(logn)

当数据增大n倍时，耗时增大logn倍。

#include<iostream>  using namespace std;  int main(){  	int n=0;  	cin>>n;  	for(int i=0;i<n;i++){  	   i*=2;  	   cout<<i;  	}  	return 0;  }

本来循环次数是n，现在i*=2了。那么答案是log(2)(n)。

反着想也可以，原来循环n次，现在每次i变成原来的2倍，也就是2的k次方等于n。那么正好就是log(2)(n)，即O(log n)

或者下面这样：

#include<iostream>using namespace std;  int main(){  int n=0;  cin>>n;  while((n=n/2)>0){      cout<<n;  }   return 0;  }

时间复杂度也是O(logn)

五、O(nlogn)

一般归并排序和堆排序是O(nlogn)。 

常见的是外层循环的时间复杂度是n，内层循环的时间复杂度是logn。

比如下面这样：

for(int i=1; i<=n; i++)  {  	for(int j=1; j<=n; j+=i)  	{  		.....   //复杂度为O(1);  	}  }

注意：外层循环是n，内层循环j每次都增加i。