[LintCode/LeetCode] Check Sum of K Primes

lakeside 發(fā)布于2019-08-16 12:37 / 2034人閱讀

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云服務(wù)器云服務(wù)器 Primes check sum Double-Check

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/71399.html

相關(guān)文章

[LintCode/LeetCode] Super Ugly Number

摘要：建兩個新數(shù)組，一個存數(shù)，一個存。數(shù)組中所有元素初值都是。實現(xiàn)的過程是，一個循環(huán)里包含兩個子循環(huán)。兩個子循環(huán)的作用分別是，遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積，結(jié)果與相同的，就將加，即跳過這個結(jié)果相同結(jié)果只存一次。 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

摘要：看到這個題目，怎樣可以不把它當(dāng)成一個環(huán)路來分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點四個參數(shù)。大體上說，只要，一定有解。所以跳過這個耗油量很大的油站，然后將下一個油站作為起點繼續(xù)判斷即可。 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

摘要：這個題和的做法基本一樣，只要在循環(huán)內(nèi)計算和最接近的和，并賦值更新返回值即可。 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

摘要：雙指針法的解法。然后用和夾逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組。對于這三個數(shù)，如果循環(huán)的下一個數(shù)值和當(dāng)前數(shù)值相等，就跳過以避免中有相同的解。 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

摘要：就不說了，使用的解法思路如下建立，對應(yīng)該元素的值與之差，對應(yīng)該元素的。然后，循環(huán)，對每個元素計算該值與之差，放入里，。如果中包含等于該元素值的值，那么說明這個元素正是中包含的對應(yīng)的差值。返回二元數(shù)組，即為兩個所求加數(shù)的序列。 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