線性篩求素數 線性篩求因子個數 線性篩求因子合

普通線性篩篩素數

#include<stdio.h>
#define max_n 10005
int num[max_n]={0}
int main(){
	for(int i=2;i<max_n;i++){
		if(num[i]==0){
	  	num[++num[0]]=i;
		}
		for(int j = 1; j <= num[0] ; j++){
				if(i * num[j] > max_n) break;
				num[i * num[j]]=1;
				if(i % num[j]==0)break;	
		}	
	}
return 0;
}
           

線性篩求因子個數

#include<stdio.h>
#define max_n 10005
int num[max_n]={0};
int prime_num[max_n]={0};
int snum[max_n]={0};
int main(){
	for(int i=2;i<max_n;i++){
		if(num[i]==0){
	  		num[++num[0]]=i;
	  		snum[i] = 2;
	  		prime_num[i] = 1;
		}
		for(int j = 1; j < =num[0] ; j++){
				if(i * num[j] > max_n) break;
				num[i * num[j]]=1;
				if(i % num[j]==0){
					prime_num[i * num[j]]=prime_num[i] + 1;
					snum[i * num[j]] = snum[i] / (prime_num[i] + 1) * (prime_num[i] + 2);
					break;
				}else{
					snum[ i * num[j] ] = snum[i] * snum[num[j]];
					prime_num[ i * num[j] ] = 1;
				}	
		}	
	}
return 0;
}
           

線性篩求因子合

#include<stdio.h>
#define max_n 10005
int num[max_n]={0};
int fnum[max_n + 5]={0};
int min_num[max_n+5]={0};
void init(){
	for(int i=2;i<max_n;i++){
		if(num[i]==0){
	  	num[++num[0]]=i;
	  	min_num[i]=1;
	  	fnum[i]= 1 + i;
}
		for(int j = 1; j <= num[0] ; j++){
				if(i * num[j] > max_n) break;
				num[i * num[j]]=1;
				if(i % num[j]==0){
						min_num[num[j] * i]=min_num[i] + 1;
						fnum[num[j] * i] = fnum[i] / (pow(num[j],min_num[i]+1)-1)*( pow(num[j],min_num[i]+2)-1);
				}else{
				min_num[num[j]*i] = 1;
				fnum[ i * num [ j ]] =fnum[num[j]]*fnum[i]; 
				}	
		}	
	}
return ;
}