C++実現素数の求め方

882 ワード

素数の定義:
簡単に言えば、素数は1とそれ自体で割り切れる数です.例えば2,3,5,7等は素数
コード実装:
(1)最も簡単な方法は、1つの数が素数nであるかどうかを判断することであり、2−(n−1)でこの数をそれぞれ除去し、1つが除去されれば、その数は素数ではなく、そうでなければ素数である.
(2)最適化:2—(n-1)を判断する必要はなく、2—n/2または2—n開平方を判断するだけでよい
#include
using namespace std;
#include

bool IsPrime(int num)	//num        
{
	//for (int i = 2; i < num - 1; i++)		//      
	//for (int i = 2; i < num/2; i++)		//        
	for (int i = 2; i < sqrt(num); i++)		//        
	{
		if (num%i == 0)
		{
			return false;
		}
	}
	return true;
}

int main()
{
	int num = 0;
	cout<> num;
	if (IsPrime(num))
	{
		cout << num << "   " << endl;
	}
	else
	{
		cout << num << "    " << endl;
	}
	system("pause");
	return 0;
}