计算100以内的素数

以你之姓@ 2022-08-11 07:29 179阅读 0赞

素数：又叫质数，只能被自己和1整除的数。

它的乘因子只有两个。

容易理解的计算办法

package com.zhiru;
 
 public class PrimeNumber {
 
 	//计算乘因子个数
 	public static int caluYinShu(int a){
 		int count=0;
 		//System.out.print(""+a+":");
 		for(int i=1;i<=a;i++){
 			if((a%i)==0){
 				//System.out.print(i);
 				count++;
 			}
 				
 		}
 		//System.out.print("\n");
 		return count;
 		
 	}
 	public static void main(String[] args) {
 		// TODO Auto-generated method stub
 
 	
 		// for(int i=1;i<=10;i++){
 		// caluYinShu(i);
 		// }
 		for(int j=2;j<=100;j++){
 			if(caluYinShu(j)==2)
 				System.out.print("素数:"+j);
 		}
 	}
 
 }

素数:2素数:3素数:5素数:7素数:11素数:13素数:17素数:19素数:23素数:29素数:31素数:37素数:41素数:43素数:47素数:53素数:59素数:61素数:67素数:71素数:73素数:79素数:83素数:89素数:97

高效率的计算办法

参考博客：http://blog.csdn.net/liukehua123/article/details/5482854

#include "stdafx.h"
 #include <iostream>
 using namespace std;
 
 int _tmain(int argc, _TCHAR* argv[])
 {
 	system("chcp 936");
 	int n;
 	cin >> n;
 	bool prime[1000];
 	//第一步先将偶数下标的标为false,奇数下标的标为true

<pre id="best-content-21108698" accuse="aContent" class="best-text mb-10" style="margin-top: 0px; margin-bottom: 10px; padding: 0px; font-family: arial, 'courier new', courier, 宋体, monospace; white-space: pre-wrap; word-wrap: break-word; color: rgb(51, 51, 51); font-size: 14px; line-height: 24px; background-color: rgb(241, 254, 221);">//除了0和2以外所有的偶数一定是合数

for (int i = 1; i <= n; i++)\{if (i % 2 == 0)prime\[i\] = false;elseprime\[i\] = true;\}

//质数的倍数即为合数，将合数下标的prime数组中的值改为false

//最终筛选出素数.
 	for (int x = 3; x < sqrt(n); x += 2){
 		if (prime[x]){
 			for (int j = 2 * x; j <= n; j += x) prime[j] = false;
 		}
 	}

//将数组中值为true的下标输出，即为素数.
 	for (int m = 1; m <= n; m++){
 		if (prime[m])
 			cout << m<<" ";
 	}
 	system("pause");
 	return 0;
 }