PAT 1013素数C++

PAT 1013数素数タイトル:1013数素数(20点)P iにi番目の素数を示す.現在2つの正の整数M≦N≦10 000を与えて、PMからPNまでのすべての素数を出力してください.
入力形式:1行にMとNを入力し、その間をスペースで区切ります.
出力形式:出力はP MからP Nまでのすべての素数で、10個の数字ごとに1行を占め、その間はスペースで区切られているが、行末に余分なスペースがあってはならない.
入力サンプル:5 27出力サンプル:11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 83 89 97 101コード:

#include
#include
using namespace std;

int main()
{
     
	int M,N;
	cin>>M>>N;
	int a[10000];    //     ，             
	int k=0,m=0;
	int flag;
	int i=2;
	a[0]=2;      //       
	while(k<=N) 
	{
     
		flag=0;
		for(int j=2;j<=sqrt(double(i));j++)    //1.sqrt()   double    ， i int  ，     
		                                       //2.    j
		{
     
			if(i%j==0)
			{
     
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
     
			k++;
			a[k]=i;
		}
		i++;
	}
	for(int i=M;i<N;i++)
	{
     
		cout<<a[i];
		m++;
		if(m%10==0)     //      
			cout<<endl;
		else
			cout<<' ';
	}
	cout<<a[N];
	system("pause");
	return 0;
}

注意:

最初は、forループを使用して値を制限していましたが、iの範囲を特定することはできませんでした.ネットで調べてみると10000番目の素数は10500くらいですが、毎回10000個の素数を計算するのは不便です.実行タイムアウトが発生し、4番目のテストポイントが通じないという問題も発生する可能性があります.その後whileサイクルを選んで改善しました.for(int i=0;i<10500;i++) { }

最初に1つの数iが素数であるかどうかを判断するとき、私はiを2からi-1までのすべての数で割って、残りが0であるかどうかを見ます.これにより、実行タイムアウトが発生し、4番目のテストポイントが通過しますが、改善して、iを2からsqrt(i)までのすべての数で割って、これはこの問題が考察する点かもしれません.適切な最適化プログラムを学ぶ必要があります.