shushu.cpp

YOUHSN有关“数数”代码

// ShuShu.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//===============stupid=============
//算法思想:任何一个素数是公约数只有1和它本身的数,要验证
//从2到n-1的数,如果从2到n-1有一个能够被n整除,则为素数
bool is_stupid_shushu(int n)
{
	int i;
	for(i=2;i<n;i++)
	{
		if(n%i==0) break;
	}
	if(i<n) return false;//当i==n时候,验证完毕,为素数
	else return true;

}
//===============smart===============
//另外的一种效率比较高的求一个数是否是素数的方法
//只需要验证2到sqrt(n)的数
bool is_smart_shushu(int n)
{
	int k;
	int i;
	k=sqrt(n);
	for(i=2;i<=k;i++)
	{
		if(n%i==0) 
		{
			return false;
		}
	}
	if(i>k) return true;
}
int main(int argc, char* argv[])
{
	int n;
	int control_line=0;
	cout<<"Input a number to test:"<<endl;
	cin>>n;
//	if(is_smart_shushu(n)) cout<<n<<"is shushu"<<endl;
//	else cout<<n<<"is not shushu"<<endl;
	for(int i=2;i<=n;i++)
	{
		if(is_smart_shushu(i))
		{
			cout<<i<<" ";
			control_line++;
			if(control_line%10==0) cout<<endl;

		}
	}

	return 0;
}