[LintCode/LeetCode] Check Sum of K Primes

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

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;
    }
}

云服務(wù)器 GPU云服務(wù)器 Primes check sum Double-Check

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71399.html

相關(guān)文章

[LintCode/LeetCode] Super Ugly Number

摘要：建兩個(gè)新數(shù)組，一個(gè)存數(shù)，一個(gè)存。數(shù)組中所有元素初值都是。實(shí)現(xiàn)的過(guò)程是，一個(gè)循環(huán)里包含兩個(gè)子循環(huán)。兩個(gè)子循環(huán)的作用分別是，遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積，結(jié)果與相同的，就將加，即跳過(guò)這個(gè)結(jié)果相同結(jié)果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 評(píng)論0 收藏0
[LintCode/LeetCode] Gas Station

摘要：看到這個(gè)題目，怎樣可以不把它當(dāng)成一個(gè)環(huán)路來(lái)分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點(diǎn)四個(gè)參數(shù)。大體上說(shuō)，只要，一定有解。所以跳過(guò)這個(gè)耗油量很大的油站，然后將下一個(gè)油站作為起點(diǎn)繼續(xù)判斷即可。 Problem There are N gas stations along a circular route, where the amount ...

hedge_hog 2019-08-14 15:21 評(píng)論0 收藏0
[LintCode/LeetCode] 3Sum Closest

摘要：這個(gè)題和的做法基本一樣，只要在循環(huán)內(nèi)計(jì)算和最接近的和，并賦值更新返回值即可。 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 評(píng)論0 收藏0
[LintCode/LeetCode] 3Sum

摘要：雙指針?lè)ǖ慕夥?。然后用和夾逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組。對(duì)于這三個(gè)數(shù)，如果循環(huán)的下一個(gè)數(shù)值和當(dāng)前數(shù)值相等，就跳過(guò)以避免中有相同的解。 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 評(píng)論0 收藏0
[LintCode/LeetCode] Two Sum

摘要：就不說(shuō)了，使用的解法思路如下建立，對(duì)應(yīng)該元素的值與之差，對(duì)應(yīng)該元素的。然后，循環(huán)，對(duì)每個(gè)元素計(jì)算該值與之差，放入里，。如果中包含等于該元素值的值，那么說(shuō)明這個(gè)元素正是中包含的對(duì)應(yīng)的差值。返回二元數(shù)組，即為兩個(gè)所求加數(shù)的序列。 Problem Given an array of integers, find two numbers such that they add up to a s...

xiaoxiaozi 2019-08-14 15:22 評(píng)論0 收藏0