素数_面试中常考

概念

只有1和它本身两个正因数的自然数,叫质数(Prime Number)。

(如:由2÷1=2,2÷2=1,可知2的因数只有1和它本身2这两个约数,所以2就是质数。

与之相对立的是合数:“除了1和它本身两个因数外,还有其它因数的数,叫合数。

”如:4÷1=4,4÷2=2,4÷4=1,很显然,4的因数除了1和它本身4这两个因数以外,还有因数2,所以4是合数。) 100以内的质数有: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,在100内共有25个质数。 注:

(1)1既不是质数也不是合数。因为它的约数有且只有1这一个因数。 (2)2和3是所有素数中唯一两个连着的数。 (3)2是唯一一个为偶数的质数。

下面用java实现打印出1到100内的所有质素:

 1 /**
 2  * 
 3  */
 4 package com.b510.parmnumber;
 5 
 6 /**
 7  * 质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数
 8  * @author hongten(hongtenzone@foxmail.com)<br>
 9  * @date 2013-5-22
10  */
11 public class MyMethod {
12     public static void main(String[] args) {
13         int result = getTimes();
14         System.out.println("100以内的质素有 ["+result+"]个!");
15     }
16     
17     /**
18      * 获取质素的个数
19      * @return
20      */
21     public static int getTimes(){
22         int result = 0;
23         for (int i = 2, j = 0; i <= 100; i++) {
24             if (prime(i)) {
25                 System.out.printf("%5d", i);
26                 j++;
27                 if (j % 5 == 0 && j != 0) {
28                     System.out.println();
29                 }
30             }
31             result = j;
32         }
33         return result;
34     }
35     
36     /**
37      * 判断是否为素数的方法
38      * 
39      * @param num 
40      * @return
41      */
42     public static boolean prime(int num) {
43         //2本身是质素,所以这里需要首先判断
44         if (num == 2)
45             return true;
46         boolean flag = true;
47         //如果当num大于2的时候,循环2到(num-1),如果在循环过程中
48         //有被num整除的数,说明num不是质素
49         for (int m = 2; m <= (num - 1); m++) {
50             if (num % m == 0) {
51                 flag = false;
52                 break;
53             }
54         }
55         return flag;
56     }
57 }

运行效果:

    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
100以内的质素有 [25]个!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1430 素数判定

1430 素数判定 题目描述 Description 质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。 素数在数论中有...

37060
来自专栏ml

NYOJ-----素数环

素数环 时间限制:1000 ms  |           内存限制:65535 KB 难度:2 描述 有一个整数n,把从1到n的数字无重复的排列成环,且使每相...

31160
来自专栏LhWorld哥陪你聊算法

【Spark篇】---Spark中Transformations转换算子

Spark中默认有两大类算子,Transformation(转换算子),懒执行。action算子,立即执行,有一个action算子 ,就有一个job。

11940
来自专栏数据结构与算法

1008 选数 2002年NOIP全国联赛普及组

1008 选数 2002年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 ...

29770
来自专栏ccylovehs

原反补码

17510
来自专栏ACM小冰成长之路

HDU-5558-Alice's Classified Message

ACM模版 描述 ? 题解 image.png 参考博客:Gatevin’s blog 代码 #include <iostream> #include <alg...

232100
来自专栏ACM算法日常

求素数(暴力枚举)-HDU 3823

Besides the ordinary Boy Friend and Girl Friend, here we define a more academic ...

15340
来自专栏Fish

蓝桥杯 幸运数

先说题意。题意有点长,我还是复制粘贴吧。。。 问题描述 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。 首先从1开始写出自然数1,...

33760
来自专栏猿人谷

求大于整数m且紧靠m的k个素数 及 判断一个数是否为素数的方法

题目:   请编写一个函数void fun(int m,int k ,int xx[]),该函数的功能是:将大于整数m且紧靠m的k个素数存入xx所指的数组中。 ...

39060
来自专栏码匠的流水账

聊聊storm的PartialKeyGrouping

storm-core-1.2.2-sources.jar!/org/apache/storm/grouping/PartialKeyGrouping.java

12820

扫码关注云+社区

领取腾讯云代金券