소수구하기/임인택

#include <iostream.h>
#include <math.h>
#include <time.h>

int main()
{
	int tmp_arr[10000]={2,0};
	int cur_arr_index = 1;
	int i,j;
	bool flag;

	clock_t t = clock();
	

	for(i=3; i<50000; i++)	{
		flag = true;
		for(j=0; tmp_arr[j]<=sqrt(i); j++)
		//for(j=0; j<cur_arr_index; j++)
		{
			if(i%tmp_arr[j]==0)	{
				flag=false;
				break;
			}
			else continue;
		}
		if(flag) tmp_arr[cur_arr_index++]=i; 
	}

	/*double ti = clock()-t;
	double clk = CLOCKS_PER_SEC;
	cout << ti/clk << endl;*/

	/*for(i=0; i<cur_arr_index; i++)
		cout << tmp_arr[i] << ' ';*/

	
	double ti = clock()-t;
	double clk = CLOCKS_PER_SEC;
	cout << ti/clk << endl;

	return 0;
}
 

DeleteMe 50000까지의 소수는 총 5133개입니다. 위 코드는 더 많은 숫자를 출력합니다. sqrt부분을 잘 생각해 보세요.

  for(j=0; tmp_arr[j]<sqrt(i); j++) 
 이 부분을 
    for(j=0; tmp_arr[j]<=sqrt(i); j++)   
 이렇게 수정했더니 되는군요. 등호하나때문에 결과가 엄청나게 달라지는군요. 지적해 주셔서 감사 - 임인택 (radiohead4us)

---

소수구하기