求素數

輸入M、N，1 < M < N < 1000000，求區間[M,N]內的所有素數的個數。素數定義：除了1以外，只能被1和自己整除的自然數稱為素數

輸入描述:

兩個整數M，N

輸出描述:

區間內素數的個數 示例1

輸入

2 10

輸出

4

?

#include<iostream> #define K 1000001 using namespace std; char p[K+1] = {1,1,0}; //數組前三個數 0 1 2 分別為 合數、合數、素數 int main() {int i,j;for(i = 2; i <= K/10; ++i) //防止p[i*j]越界 {if(!p[i])for(j = 2; i*j <=K ; ++j) //判斷是否為合數 p[i*j] = 1; //是合數 } int M,N,count;cin>>M;cin>>N;count=0;for(i=M; i<=N; i++)if(!p[i]) //如果p[i]為合數，則跳過，如果為素數，執行count count++;cout<<count; }

?

分析：

由素數的概念在大于1的整數中，只能被1和自己本身整除的數。

在大于1的整數中，只要類似 m*n 得到的數都不是素數。用 1 表示非素數，用 0 表示素數。則： p[i*j] = 1 即為找出所有的非素數。

K/10 是為了防止 p[i*j] 越界，當然除以20、30也是可以的！

?

參考資料鏈接：

【模板小程序】求小于等于N范圍內的質數

?？途W解答

?

最大差值

給定一個未排序的數列，找到此數列在已排序狀態下的兩個相鄰值的最大差值，少于兩個值時返回0。例如：給定數列 [1,3,2,0,1,6,8] 則 最大差值為3。注意：請盡量使用時間復雜度為O(n)的方案。

輸入描述:

第一行輸入單個整數N作為數列的大小，第二行輸入所有數列中的元素M，共N個。0 < N <= 1000000, 0 < M < 2100000000

輸出描述:

數列的最大差值 示例1

輸入

3 1 10 5

輸出

5

?

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){int N;while(cin>>N){vector<int> array(N);for(int i=0;i<(int)array.size();++i){cin>>array[i];}sort(array.begin(),array.end()); //先排序 vector<int> chazhi(N); //開一個數組，存入相鄰元素差值chazhi[0] = 0; //數組初始化 int max_chazhi = 0;for(int i=1;i<(int)chazhi.size();++i){chazhi[i]=array[i]-array[i-1];max_chazhi = chazhi[i]>max_chazhi ? chazhi[i]: max_chazhi;}cout<<max_chazhi<<endl;}return 0; }

?

分析：

研究了一下別人的代碼，整體思路就是先對輸入的數列進行從小到大的排序，接著創建一個數組，存入排序后相鄰兩個數之間的差值，接著再挨個比較大小，最后輸出最大差值。

?

參考資料鏈接：

?？途W解答

vector

algorithm->sort

?

轉載于:https://www.cnblogs.com/OctoptusLian/p/8665631.html

總結

以上是生活随笔為你收集整理的【吉比特】G-bits2017技术类岗位编程题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。