[LintCode/LeetCode] Check Sum of K Primes

lakeside 发布于2019-08-16 12:37 / 2033人阅读

Problem

Given two numbers n and k. We need to find out if n can be written as sum of k prime numbers.

Example

Given n = 10, k = 2
Return true // 10 = 5 + 5

Given n = 2, k = 2
Return false

Solution

public class Solution {
    /**
     * @param n: an int
     * @param k: an int
     * @return: if N can be expressed in the form of sum of K primes, return true; otherwise, return false.
     */
     //https://blog.csdn.net/zhaohengchuan/article/details/78673665
    public boolean isSumOfKPrimes(int n, int k) {
        // write your code here
        if (k*2 > n) return false; //the minumum prime is 2, so is impossible
        if (k == 1) return isPrime(n); //has to be prime itself
        
        // Based on: any even number is the sum of an even number of primes!
        if (k%2 == 1) {
            if (n%2 == 1) return isSumOfKPrimes(n-3, k-1);
            else return isSumOfKPrimes(n-2, k-1);
        } else {
            if (n%2 == 1) return isSumOfKPrimes(n-2, k-1);
            else return true;
        }
    }
    private boolean isPrime(int n) {
        if (n < 2) return false;
        else {
            for (int i = 2; i < n/2+1; i++) {
                if (n%i == 0) return false;
            }
        }
        return true;
    }
}

云服务器 GPU云服务器 Primes check sum Double-Check

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71399.html

[LintCode/LeetCode] Super Ugly Number

摘要：建两个新数组，一个存数，一个存。数组中所有元素初值都是。实现的过程是，一个循环里包含两个子循环。两个子循环的作用分别是，遍历数组与相乘找到最小乘积存入再遍历一次数组与的乘积，结果与相同的，就将加，即跳过这个结果相同结果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 评论0 收藏0
[LintCode/LeetCode] Gas Station

摘要：看到这个题目，怎样可以不把它当成一个环路来分析，以及减少多余的空间呢例如，我们引入单次剩余油量，剩余油量和，总剩余油量和，以及可行起点四个参数。大体上说，只要，一定有解。所以跳过这个耗油量很大的油站，然后将下一个油站作为起点继续判断即可。 Problem There are N gas stations along a circular route, where the amount ...

hedge_hog 2019-08-14 15:21 评论0 收藏0
[LintCode/LeetCode] 3Sum Closest

摘要：这个题和的做法基本一样，只要在循环内计算和最接近的和，并赋值更新返回值即可。 Problem Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three intege...

ShevaKuilin 2019-08-14 15:42 评论0 收藏0
[LintCode/LeetCode] 3Sum

摘要：双指针法的解法。然后用和夹逼找到使三数和为零的三数数列，放入结果数组。对于这三个数，如果循环的下一个数值和当前数值相等，就跳过以避免中有相同的解。 Problem Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplet...

Sunxb 2019-08-14 15:42 评论0 收藏0
[LintCode/LeetCode] Two Sum

摘要：就不说了，使用的解法思路如下建立，对应该元素的值与之差，对应该元素的。然后，循环，对每个元素计算该值与之差，放入里，。如果中包含等于该元素值的值，那么说明这个元素正是中包含的对应的差值。返回二元数组，即为两个所求加数的序列。 Problem Given an array of integers, find two numbers such that they add up to a s...

xiaoxiaozi 2019-08-14 15:22 评论0 收藏0