黑马程序员技术交流社区

标题: 素数算法 [打印本页]

---

作者: 825176857    时间: 2015-7-16 00:21
标题: 素数算法
素数：只能被1和它本身整除


算法:首先1和2是素数,如果一个数能够被从2到它平方根之间某个数整除它就不是素数


Java 列出 2 - 100 之间的所有素数
TestPrime.java
public class TestPrime {  

         

     public static boolean isPrime(int num) {     

        for(int i = 2; i <= Math.sqrt(num); i++) {//程序默认2是素数，当j=2时，循环不执行  

            if(num % i == 0) {  

              return false;  

            }  

        }  

        return true;  

     }  

   

     public static void main(String[] args) {  

         for(int j = 2; j <= 100; j++) {  

             if(TestPrime.isPrime(j)) {  

                 System.out.println(j + " is a prime");  

             }  

         }        

     }  

}


简单改进：
for(int i = 2; i <= Math.sqrt(num); i++)这里每次循环都要执行一次Math.sqrt(num),而这是一个固定值，
因此应该使用空间换时间，double t = Math.sqrt(num); for(int i = 2; i <= i; i++)这样执行。



正则表达式方法:
        String str="^1?$|^(11+)\\1+$";  
        Pattern pattern=Pattern.compile(str);  
         
        StringBuffer sb = new StringBuffer();
        for(int i=1;i<1000;i++){
                                sb.append("1");
                        String tt = sb.toString();
            Matcher matcher=pattern.matcher(tt);  
            if(!matcher.matches()){  
                System.out.println(i);  
            }  
        }


这是对正则的一种很诡异的应用 不过很有意思 来判断一个数是不是包含除1以外的因子。


java中已经把\1改成\\1 在JS中用\1就可以

---

作者: 齐天大圣    时间: 2015-7-16 01:41
package Tools2;
import java.util.Scanner;
public class Test15_判断一个素数能被几个9整除 {
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                while (true) {
                        System.out.println("please data");
                        int x = sc.nextInt();
                        if (flag(x)) {getNine(x);} else {System.out.println("!prime");}}}
        private static void getNine(int n) {
                if (n <= 8) {System.out.println("是素数，有" + 0 + "个9整除");}
                if (n > 8) {System.out.println("是素数，有" + n / 9 + "个9整除");}}
        private static boolean flag(int n) {
                boolean flag = true;
                if (n <= 1) {return false;} else if (n == 2) {return true;}
                for (int x = 2; x < Math.sqrt(n) + 1; x++) {
                if (n % x == 0) {flag = false;}}return flag;}}

---

作者: 齐天大圣    时间: 2015-7-16 01:43
package Tools2;
import java.util.Scanner;
public class Test14_判断一个偶数是否2个素数和 {
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                while (true) {
                        System.out.println("please one  even");
                        int x = sc.nextInt();
                        if (x <= 0 || x % 2 != 0) {
                                System.out.println("数据错误");
                                //return;
                        } else {
                                boolean flag = addPrime(x);
                                System.out.println(flag);
                        }
                }
        }

        // 素数判断
        private static boolean isPrime(int n) {
                boolean flag = true;
                for (int x = 2; x < (Math.sqrt(n) + 1); x++) {
                        if (n % x == 0) {
                                flag = false;
                                break;
                        }
                }
                return flag;
        }
        private static boolean addPrime(int n) {
                boolean flag = false;
                for (int x = 2; x < n / 2; x++) {
                        if (isPrime(x) == true && isPrime(n - x) == true) {
                                flag = true;
                        }
                }
                return flag;
        }
}

---

作者: 齐天大圣    时间: 2015-7-16 01:45
//判断素数
public static boolean isPrime(long n) {
                boolean flag = true;
                if (n <= 3) {
                        return n > 1;
                }
                if (n % 2 == 0 || n % 3 == 0) {
                        return false;
                }
                for (int i = 5; i * i <= n; i += n) {
                        if (n % i == 0 || n % (i + 2) == 0) {
                                return false;
                        }
                }
                return true;
        }

---

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

黑马程序员IT技术论坛 X3.2