首页 > 编程语言 > 详细

杭电oj 2098——分拆素数和(包含如何判断质数及优化),java实现

时间:2020-01-11 21:48:32      阅读:143      评论:0      收藏:0      [点我收藏+]

question:分拆素数和

技术分享图片

 

 

思路:

1.首先从1一直遍历到数据的1/2位置(因为后面的会和前面的重复),因为是要两个数,所以另一个数就是原数据减去遍历的数字(即i 和data-i),如果二者同时为质数的话,分拆方法计数器就加一,最后输出计数器即可

2.关于如何判断质数,其实就是找约数,数本身不用管,如果其余约数只有1.则为质数,最笨的方法就是从1到数据大小的遍历,这样太费时间

关于优化:

a.首先偶数不可能为质数,先一步排除

b.然后遍历的时候上限为该数的平方根(具体原因不记得了/捂脸)

c.循环的累加可优化为i+=2,因为如果可以被偶数整除,则一定可以被二整除,前面已经排除过了,把 i 限制为奇数就好

 

source code:

package hduoj;

import java.util.Scanner;

public class hdoj_2098 {
    static boolean check(int data){//true indicates the number is prime,false means not
        if(data<2) return false;
        if(data%2==0) return false;
        for(int i = 3;i<=Math.sqrt(data);i = i+2){
            if(data%i==0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true){
            int data = sc.nextInt();
            if(data==0) break;
            int count = 0;
            for(int i = 1;i<data/2;++i){
                if(check(i)&&check(data-i)) {
                    count++;
                    //System.out.println(i);
                }
            }
            System.out.println(count);
        }
    }
}

 

 

注:代码已经AC,贴上来的是在自己编译器里的,需要改关键字

 

希望对大家有所帮助

以上

杭电oj 2098——分拆素数和(包含如何判断质数及优化),java实现

原文:https://www.cnblogs.com/lavender-pansy/p/12180967.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!