藍橋杯真題 17省2-等差素數列 2,3,5,7,11,13,....是素數序列。 類似：7,37,67,97,127,157 這樣完全由素陣列成的等差數列，叫等差素數數列。 上邊的數列公差為30

問題描述

2,3,5,7,11,13,…是素數序列。
類似：7,37,67,97,127,157 這樣完全由素陣列成的等差數列，叫等差素數數列。
上邊的數列公差為30，長度為6。

2004年，格林與華人陶哲軒合作證明了：存在任意長度的素數等差數列。
這是數論領域一項驚人的成果！

有這一理論為基礎，請你藉助手中的計算機，滿懷信心地搜尋：

長度為10的等差素數列，其公差最小值是多少？

注意：需要輸出的是一個整數，不要填寫任何多餘的內容和說明文字。
輸入

無輸入
輸出

一個整數
提示

用printf或cout輸出答案

思路

用一個a[]陣列把100000以內的素數存起來（標記），接著從第一個素數開始往後連續找10個成等差數列的素數，找到就結束，輸出此時的公差。

程式碼：

#include <stdio.h>
int a[100000]={0};
int check(int x) {
	if(x < 2) return 0;
	for(int i = 2; i < x; i++) {
		if(x%i == 0) {
			return 0;
		}
	}
	return 1;
}
int main() {
	for(int i = 2; i < 100000; i++) {
		if( check(i) ) {
			a[i] = 1;   //說明i為素數  賦1
		}
	}
	for(int cha = 1; cha < 10000; cha++) { //公差
		for(int i = 2; i < 100000; i++ ) {  //起始位置
			int count;
			for(count= 0 ; count < 10; count++) {
				if(a[ i+count*cha ] != 1) {  //說明這個數不是素數
					break;
				}
			}
			if(count == 10) {
				printf("%d",cha);
				return 0;
			}
		}
	}
	return 0;
}