问检查一个数字是否是Smith数字
EN

Code Review用户

提问于 2017-12-20 22:27:09

回答 2查看 1.9K关注 0票数 3

我创建了一个Java程序来检查用户输入的数字是否是史密斯数 (一个数字之和等于其素数分解的数字之和)。该程序运行良好，但要检查4937775这样的数字需要太长时间。如何减少它执行所需的时间？

import java.util.*; 
class check
{
    static boolean a;
    static boolean checkprime(long n)
    {
        int i, factors= 0; 
        for(i = 1;i<=n ;i++)
        {
            if(n%i==0)
                factors++;
        }
        if(factors == 2)
            return true;
        else
            return false; 
    }

    static long sumfinder(long  n)
    {
        long  sum = 0; 
        while(n!=0)
        {
            sum = sum + n%10; 
            n= n/10; 
        }
        return sum; 
    }

    static boolean checksmith(long  n)
    {
        long  sum = 0; 
        if(checkprime(n)== true)
        { 
            System.out.println(n + " is a prime number ");
            return false; 
        }
        else
        {
            System.out.println(n + " is not  a prime number ");
            //generate prime factors: 
            long  num = n; 

            outer: 
            for(long  i = 1; i<= num ; i++)
            {
                if(checkprime(i)== true)
                {

                    if(num%i== 0)
                    {
                        sum= sum+ sumfinder(i); 
                        num = num/i; 
                        i = 1;
                        if (num == 1)
                        {
                            break outer; 
                        }
                    }
                }
            }
        }

        System.out.println(sum);
        System.out.println(sumfinder(n));

        if (sumfinder(n)== sum)

            return true; 

        else
            return false;
    }

    static void display()throws InputMismatchException
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number");
        long  n = sc.nextInt(); 
        if(checksmith(n)== true)
        {
            System.out.println("Smith number");

        }
        else
            System.out.println("Not a Smith number");
    }

    public static void main(String [] args)
    {
        display(); 
    }
}

java

time-limit-exceeded

primes

回答 2

Code Review用户

发布于 2017-12-21 04:14:17

若要分解整数，只需在2和sqrt(num)之间循环因子即可。如果n是素数，那么num现在将等于n。如果num现在不是1，那么它也是一个主要因素。

import java.util.*;
class Check {
    static long sumDigits(long n) {
        long sum = 0;
        while (n != 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    static boolean checkSmith(long n) {
        long sum = 0, num = n;
        for (long i = 2; i * i <= num; i++) {
            while (num % i == 0) {
                // i is a prime here
                sum += sumDigits(i);
                num /= i;
            }
        }
        if (n == num && n > 1) {
            System.out.println(n + " is a prime number");
            return false;
        }
        System.out.println(n + " is not a prime number");
        if (num > 1) {
            // num is a prime here
            sum += sumDigits(num);
        }

        System.out.println(sum);
        System.out.println(sumDigits(n));

        return sumDigits(n) == sum;
    }

    static void display() throws InputMismatchException {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number:");
        long n = sc.nextLong();
        if (checkSmith(n))
            System.out.println("Smith number");
        else
            System.out.println("Not a Smith number");
    }

    public static void main(String[] args) {
        display();
    }
}

票数 2

Code Review用户

发布于 2017-12-20 22:47:45

一些改进的想法：

在checkprime中，您不必从1循环到n，从1循环到sqrt(n)就足够了。
outer循环效率很低。首先，每次您找到一个因素时，从一开始就开始寻找更多的因素，在已经检查过的数字上调用checkprime。第二，我不会费心检查从1到n的任何数字的checkprime，我会对除数进行检查。

一个更有效的循环是：

 for(long  i = 1; i<= num ; i++)
    {
        if(num%i== 0 && checkprime(i))
        {
           sum= sum+ sumfinder(i); 
           num = num/i; 
           if (num == 1)
           {
               break outer; 
           }
        }
        i--; //check same factor again
    }