Мой код работает, только когда вход ниже 31 [ProjectEuler100] задача № 10-Суммирование простых чисел - PullRequest
Новая
       1

Мой код работает, только когда вход ниже 31 [ProjectEuler100] задача № 10-Суммирование простых чисел

0 голосов
/ 22 января 2020

Проблема из проекта Euler100.

Мой код должен находить сумму простых чисел ниже n.

Работает нормально, только когда n меньше 31.

Когда n равно 32, я все еще получил 129, когда n равно 2001, я все еще получил 129. (Сумма простых чисел ниже 29, включая 29, равна 129, поэтому, если n равно 32, предполагается, что он вернется 160).

Я не понимаю, почему ... Вот мой код (python) 


# Except 2 and 3, primes are written in the form of 6k±1.(edited)
import math

def is_prime(number):
    for i in range(2, int(math.sqrt(number))+1):
        if number % i == 0:
            return False
        else:
            continue
    return True

def prime_summation(n):
    prime_sum = 0
    prime_i = [5, 7]

    if int(n) == 3:
        prime_sum = 2
    elif int(n) < 5 and int(n) > 3:
        prime_sum = 5
    elif int(n) >= 5:
        prime_sum = 5  #2 + 3 = 5
        for prime in prime_i:
            while prime < int(n) and is_prime(prime):

                prime_sum += prime
                prime += 6

    return prime_sum

if __name__ == '__main__':
    n = input("Sum of primes below n, n ?: ")
    print(prime_summation(n))

Ответы [ 3 ]

1 голос
/ 22 января 2020

Мне кажется, что это сработает, если вы переписываете его так (не вырывайте из while -l oop, если вы встретите какие-либо непростые простые числа, например, 25). 

def prime_summation(n):
    n = int(n)

    prime_i = [5, 7]
    prime_sum = 0

    if n == 3:
        prime_sum = 2
    elif n == 4:
        prime_sum = 5
    elif n >= 5:
        prime_sum = 5  #2 + 3 = 5
        for prime in prime_i:
            while prime < n:
                if is_prime(prime):
                    prime_sum += prime
                prime += 6
    return prime_sum
0 голосов
/ 22 января 2020

Я нашел ответ, ребята, лол, потому что я установил условие while l oop следующим образом: while prime < int(n) and is_prime(prime)

Останавливает l oop после 25 (25 = 6 * 4 +1).

Я изменил свой код на: 

 while prime < int(n):
                if is_prime(prime):
                    prime_sum += prime
                prime += 6

и все работает!

0 голосов
/ 22 января 2020

То же решение написано в Go: 

package problem10

import (
    "log"
    "math"

    "github.com/alessiosavi/GoGPUtils/helper"
    mathutils "github.com/alessiosavi/GoGPUtils/math"
)

// IsPrime is delegated to verify if the given number is prime
func IsPrime(n int) bool {
    if n <= 3 {
        return n > 1
    } else if n%2 == 0 || n%3 == 0 {
        return false
    }
    i := 5
    mult := float64(2)
    for int(math.Pow(float64(i), mult)) <= n {
        if n%i == 0 || n%(i+2) == 0 {
            return false
        }
        i += 6
    }
    return true
}

func CalculatePrime(max int) {
    // generate an array of sequential number like [1,2,3,4,5,..., max]
    array := helper.GenerateSequentialIntArray(max)
    var prime []int
    for i := 0; i < len(array); i++ {
        if IsPrime(array[i]) {
            prime = append(prime, array[i])
        }
    }
    // Sum all the value present in the array -> [1,3,5] --> 9
    log.Println(mathutils.SumIntArray(prime))
}

https://github.com/alessiosavi/GoProjectEuler

...