判断一个数是否为素数

àì夳堔傛蜴生んèń 2023-06-15 13:24 7阅读 0赞

*  **判断一个数是否为质数：质数是指大于1的自然数中除1与自身外没有其他因数**

#include<iostream>
    using namespace std;
    //判断一个数是否为质数：质数是指大于1的自然数中除1与自身外没有其他因数
    void main() {
        
    	int i, count = 0;
    	cin >> i;
    	if (i == 1) {
        
    		cout << i << "不是素数" << endl;
    		return;
    	}
    	if (i == 2) {
        
    		cout << i << "是素数" << endl;
    		return;
    	}
    	for (int k = 2; k < i; k++) {
        //判断2-（i-1）之间有没有能被整除的数
    		if (i % k == 0) {
        
    			count++;
    		}
    	}
    	if (count == 0) {
        
    		cout << i << "是素数" << endl;
    	}
    	else {
        
    		cout << i << "不是素数" << endl;
    	}
    }

方法二：可以不用比较2-(i-1)之间的所有数，只需比较2-(根号i)之间的数
    #include<iostream>
    using namespace std;
    //判断一个数是否为质数：质数是指大于1的自然数中除1与自身外没有其他因数
    void main() {
        
    	int i,j, count = 0;
    	cin >> i;
    	if (i == 1) {
        
    		cout << i << "不是素数" << endl;
    		return;
    	}
    	if (i == 2) {
        
    		cout << i << "是素数" << endl;
    		return;
    	}
    	j = (int)sqrt(i);
    	for (int k = 2; k < =j; k++) {
        //判断2-sqrt(i)之间有没有能被整除的数
    		if (i % k == 0) {
        
    			count++;
    		}
    	}
    	if (count == 0) {
        
    		cout << i << "是素数" << endl;
    	}
    	else {
        
    		cout << i << "不是素数" << endl;
    	}
    }

运行结果  
![素数][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyNjc4_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyNjc4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191122162447907.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyNjc4,size_16,color_FFFFFF,t_70