a626 - 6. Prime Directive

🔗 前往 ZeroJudge 原題

題目描述

題目要求輸出從 2 到給定正整數 N (1 ≤ N ≤ 1000) 的所有質數，並按照每行五個數字的格式輸出。

解題思路

本題採用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 來找出指定範圍內的質數。首先，建立一個布林陣列 a，用於標記每個數字是否為質數。初始時，所有數字都標記為質數 (0)。然後，從 2 開始，將所有 2 的倍數標記為非質數 (1)。接著，找到下一個未被標記為非質數的數字，重複上述步驟，直到篩選完畢。最後，遍歷陣列 a，輸出所有標記為質數的數字，並按照每行五個數字的格式輸出。

複雜度分析

• 時間複雜度: O(N log log N) (埃拉托斯特尼篩法的時間複雜度)
• 空間複雜度: O(N) (使用大小為 N+1 的布林陣列)

程式碼

#include <stdio.h>
int a[1001]={0};
int main(){
	for(int i=2;i<=32;i++){
		if(a[i]==0)
			for(int j=i*2;j<=1000;j+=i)
				a[j]=1;
	}
	int b;
	while(scanf("%d",&b)>0){
		int c=1;
		for(int i=2;i<=b;i++){
			if(a[i]==0){
				printf("%10d",i);
				if(c%5==0)printf("\n");
				c++;
			}
		}
		printf("\n");
	}
}