黑马程序员技术交流社区

标题: 素数 咋么求？ [打印本页]
作者: 张可可    时间: 2016-6-6 22:12
标题: 素数 咋么求？
需求：用代码实现101-999之间的素数
作者: ancheng    时间: 2016-6-7 00:30
  1. //第一种解法
  2. public class Ancheng {

  4.         public static void main(String[] args) {

  6.                 for (int i = 100; i < 1000; i++) {
  7.                         if (isPrime(i)) {
  8.                                 System.out.println(i);
  9.                         }
  10.                 }
  11.         }
  12.        
  13.         public static boolean isPrime(long n) {
  14.                 if (n <= 3) {
  15.                         return n > 1;
  16.                 }
  17.                 if (n % 2 == 0 || n % 3 == 0) {
  18.                         return false;
  19.                 }

  21.                 for (int i = 5; i <= Math.sqrt(n); i += 6) {
  22.                         if (n % i == 0 || n % (i + 2) == 0) {
  23.                                 return false;
  24.                         }
  25.                 }
  26.                 return true;
  27.         }
  28. }
复制代码
作者: 善良的死神达乐    时间: 2016-6-7 00:33
楼上的求素数是最简单的了...定义一个方法求素数,返回值为true,在主方法中判断,是素数就打印......应该还要定义一个计数器,打印没5个数为一行
作者: 善良的死神达乐    时间: 2016-6-7 00:35
public class Test02 {

        /**
         * 2.分析以下需求，并用代码实现： (1)打印1-100之间的所有素数及个数 (2)每行输出5个满足条件的数，之间用空格分隔
         * (3)如果一个大于1的自然数，这个数只能被1和其本身整除，这个数就叫素数。 (4)如：2 3 5 7 11
         */
        public static void main(String[] args) {
                // 定义一个计数器
                int count = 0;
                // 友情提示
                System.out.println("1到100之间的的素数有：");
                // 因为结果是从2开始的,所以去掉1,从2开始遍历
                for (int i = 2; i <= 100; i++) {
                        // 当下面的方法返回的是true时,就执行,当返回时false时,忽略它,因为我们只要满足素数条件的数
                        if (suShu(i)) {
                                // 打印素数,"\t"是tab键,为了打印格式整齐
                                System.out.print(i + "\t");
                                // 计数器统计满足素数的个数
                                count++;
                                // 让计数器计数,当每行输出五个的时候就换行
                                if (count % 5 == 0) {
                                        System.out.println();
                                }
                        }
                }
        }

        /*
         * 判断是否是素数 1.明确返回值类型 boolean 2.明确参数类型 int x
         */
        public static boolean suShu(int x) {

                for (int i = 2; i < x; i++) {
                        // 如果一个大于2的数能被2整除,那就不是素数,返回false.
                        if (x % i == 0 ) {
                                return false;
                        }
                }
                // 否则返回true
                return true;
        }
}

//有注释,看着估计会明白点,最主要在求素数的方法中,那个for循环不要被绕进去就好了
作者: ancheng    时间: 2016-6-7 07:28
  1. //第二种解法（最简单粗暴的）
  2. public class AnCheng {

  4.         public static void main(String[] args) {
  5.                 // 在素数中除了2，其他都是奇数，所以初始值如果为奇数并大于2，便可以只判断奇数以提高效率
  6.                 for (int i = 101; i <= 999; i += 2) {
  7.                         boolean flag = true;
  8.                         for (int j = 2; j < i; j++) {
  9.                                 if (i % j == 0) {
  10.                                         flag = false;
  11.                                         break;
  12.                                 }
  13.                         }
  14.                         if(flag){
  15.                                 System.out.println(i);
  16.                         }
  17.                 }
  18.         }
  19. }
复制代码
作者: ancheng    时间: 2016-6-7 07:44
  1. //第三种解法（筛选法）
  2. public class Ancheng {

  4.         public static void main(String[] args) {
  5.                 boolean[] arr = new boolean[1000];
  6.                 arr[2] = true;
  7.                 for (int i = 2; i < arr.length; i++) {
  8.                         if (i % 2 == 1) {
  9.                                 arr[i] = true;
  10.                         }
  11.                 }

  13.                 for (int i = 3; i < 1000 / 2; i += 2) {
  14.                         if (arr[i]) {
  15.                                 for (int j = 2 * i; j < 1000; j += i) {
  16.                                         arr[j] = false;
  17.                                 }
  18.                         }
  19.                 }
  20.                 for (int i = 101; i < 1000; i++) {
  21.                         if (arr[i]) {
  22.                                 System.out.println(i);
  23.                         }
  24.                 }
  25.         }
  26. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2