拆分數字x

關于長度

查找一個數n的全部因子

找出小于等于x的素數

埃氏篩法

歐拉篩法

1.拆分數字x（可以很大噢）

int x,a[10005],c=0;//a[]陣列存放拆分出來的每個數字，c用于標記數字在陣列里存放的位置
	scanf("%d",&x);
	while(x){
		a[c++]=x%10;
		x/=10;
	}
	for(int i=c-1;i>=0;i--)//正序輸出
		printf("%d ",a[i]);

2.關于長度：
字串陣列長度：strlen()
整型陣列長度：sizeof(arr)/sizeof( int )
注意：這里得到的是陣列的總長度（即我們定義它的時候的大小），而不是陣列中存放有意義的資料的個數
（實在不行就用定義一個量來追蹤它就好啦）

3.查找一個數n的全部因子：（或者是因子的個數）

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n; 
	int a[10005];//裝n的所有因子
	int z=0;//輔助陣列裝因子的位置
	scanf("%d",&n);
	for(int i=1;i*i<=n;i++){
		if(n%i==0){
			a[z++]=i;
			if(i!=(n/i)){//因為是在n/2前找所以可以用這個方法來查找n/2后的符合條件的數
				a[z++]=n/i;
			}
		}
	}
	return 0;
}

4.找出一定范圍x的素數
方法一：埃氏篩法

#include <bits/stdc++.h>
using namespace std;
int visit[100005]={0};//先假設全部都為素數
//0為素數   1為非素數 
int main() 
{
	int x;
	scanf("%d",&x);
	for(int i=2;i<=x;i++){
		if(!visit[i])
			for(int j=i*i;j<=x;j+=i) 
				visit[j]=1;
	}
	for(int i=2;i<=x;i++)
		if(!visit[i])
			printf("%d ",i);	 
    return 0;
}

這里的ii做了一個小優化，因為i(2 ~ i-1)在2~i-1時已經被篩去遼
但是，埃氏篩法有一個弊端，就是重復判斷同一個數，重復篩去同一個數，這也會浪費時間，當資料很大時也可能會超時，
為了解決這個弊端，我們引進一種新的方法：歐拉篩法，
方法二：歐拉篩法（它可以讓每個合數只被它最小的質因子篩選一次！！！_{超厲害！！！他也太聰明了叭！！！！}）

#include <bits/stdc++.h>
using namespace std;
//設0為素數  1為非素數 
int visit[100005]={0};//訪問每個位置，判斷 
int prime[100005]={0};//儲存  
int Prime(int x){
	int n=0;
	for(int i=2;i<=x;i++){
		if(!visit[i])
			prime[n++]=i;
		for(int j=0;j<n&&i*prime[j]<=x;j++){
			visit[i*prime[j]]=1;
			if(i%prime[j]==0) break;//這個得細細琢磨，是這個方法的精髓！！！ 
		}
	}
	return n; //記錄找到了多少個素數 
}
int main() 
{
	int x;
	scanf("%d",&x);
	int sum=Prime(x);
	for(int i=0;i<sum;i++){
		printf("%d ",prime[i]);
	}
	cout<<endl<<sum;
    return 0;
}

這個方法中i*prime[j] 以及i%prime[j]==0這兩步可以通過列印出每一步的程序來幫助我們理解，比如：
方便理解
我們可以看到，i在消去合數中的作用是：當做倍數來幫助代碼找到合數并消去，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/243857.html

標籤：其他

上一篇：2021/1/1-每日三題第8彈：小可愛們新年快樂呀，網頁驗證碼到底有什么用呢？？？

下一篇：制作一個頁面，頁面上放一個文本框、一個按鈕。按鈕上顯示的文本為“判斷”，并給按鈕關聯點擊事件，在事件中判斷文本框里的數是偶數還是奇數，彈出視窗顯示判斷結果。