(in python) The Sieve of Eratosthenes and Goldbach\'s Conjecture Implement the S
ID: 3858722 • Letter: #
Question
(in python)
The Sieve of Eratosthenes and Goldbach's Conjecture
Implement the Sieve of Eratosthenes and use it to find all prime
numbers less than or equal to one million. Use the result to
prove Goldbach's Conjecture for all even integers between four and
one million, inclusive.
Implement a method with the following declaration:
This function must be written to accept a list of integers of any
size. You should output for all primes numbers between 1 and
1000000, but when I test your function it may be on an list of a
different size. The number will be specified at runtime (i.e. use
the 'input' function).
Implement a method with the following declaration:
The goal here is to provide an efficient implementation. This
means no multiplication, division, or modulus when determining if
a number is prime. It also means that the second method must find
two primes efficiently.
Output for your program: All prime numbers between 1 and 1000000
and all even numbers between 4 and 1000000 and the two prime
numbers that sum up to it.
DO NOT provide output or a session record for this project!
( plz write the code in Python)
(in python)
The Sieve of Eratosthenes and Goldbach's Conjecture
Implement the Sieve of Eratosthenes and use it to find all prime
numbers less than or equal to one million. Use the result to
prove Goldbach's Conjecture for all even integers between four and
one million, inclusive.
Implement a method with the following declaration:
def sieve(list): ## your code goes hereThis function takes a list of integers as its argument. The list
should be initialized to the values 1 through 1000000. The
function modifies the list so that only the prime numbers remain;
all other values are changed to zero.
This function must be written to accept a list of integers of any
size. You should output for all primes numbers between 1 and
1000000, but when I test your function it may be on an list of a
different size. The number will be specified at runtime (i.e. use
the 'input' function).
Implement a method with the following declaration:
def goldbach(list): ## your code goes hereThis function takes the same argument as the previous method
and displays each even integer between 4 and 1000000 with two
prime numbers that add to it.
The goal here is to provide an efficient implementation. This
means no multiplication, division, or modulus when determining if
a number is prime. It also means that the second method must find
two primes efficiently.
Output for your program: All prime numbers between 1 and 1000000
and all even numbers between 4 and 1000000 and the two prime
numbers that sum up to it.
DO NOT provide output or a session record for this project!
( plz write the code in Python)
Explanation / Answer
def sieve(nlist): """ Function returns a list of prime numbers :param nlist: the limit for the list, integer :return: a list of primes """ not_prime = [] prime = [] for i in xrange(2, nlist+1): if i not in not_prime: prime.append(i) for j in xrange(i*i, nlist+1, i): not_prime.append(j) return prime def goldbach(nlist): """ Function proves the goldbach's conjecture :param nlist: list of numbers :return: """ goldbach_even = [] goldbach_prime = [] goldbach_prime_list = [] for prime in nlist: for plist in nlist: if (prime+plist)&0x1 == 0x0: goldbach_even.append(prime+plist) # the even numbers from 4 goldbach_prime.append(prime) goldbach_prime.append(plist) goldbach_prime_list.append(goldbach_prime) return goldbach_even, goldbach_prime_list if __name__ == '__main__': list_size = input("Enter list size") prime_list = sieve(int(list_size)) #print (plist) goldbach_list = goldbach(prime_list) # returns a tuple with the list containing all even numbers and a list with the two prime numbers that add up to the even number
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.