Python code

[Ntsoaki]

import sys
import random
sys.setrecursionlimit(1500)
def prime(n):
	"""
	Generate all prime numbers less than n.
	"""
	yield 2
	primes = []
	for m in range(3,n,2):
		if all(m%p for p in primes):
			primes.append(m)
			yield m

n=int(raw_input())
i=0
j=0
while(n!=-1):
	p=list(prime(n))
	sun=0
	while(sun!=n and i<1000000000000000000000000000000):
		F=random.sample(p,4)
		sun=sum(F)
		i+=1
	if(sun==n):
		for i in F:
			if(j==3):
				print i
			else:
				print i,
			j+=1
	else:
		print 'Impossible.'
	n=int(raw_input())
	i=0

Time Limit: 4 seconds
Euler proved in one of his classic theorems that prime numbers are infinite in number. But
can every number be expressed as a summation of four positive primes? Your tutors dont know
the answer. May be you can help!!! I want your solution to be very efficient as we have inefficient
machines in the honours lab. The definition of a prime number for this problem is, A prime
number is a positive number which has exactly two distinct integer factors. As for example 37
is prime as it has exactly two distinct integer factors 37 and 1.
2.2 Input:
The input contains one integer number N (N<=10000000) in every line. This is the number you
will have to express as a summation of four primes. Input is terminated by end of file.
2.3 Output:
For each line of input there is one line of output, which contains four prime numbers according to
the given condition. If the number cannot be expressed as a summation of four prime numbers
print the line “Impossible.” in a single line. There can be multiple solutions. Any good solution
will be accepted.Your program should run in a continuous loop until a ‘-1’ is entered.
2.4 Sample Input:
24
36
46
-1
2.5 Sample Output:
3 11 3 7
3 7 13 13
11 11 17 7

my code take too long so exceed time limit.can any body help i am new at python

[woooee]

I tested your code for n=100,000 and "while(sun!=n and i<100000)" instead of i < 10**30 (you aren't going to do anything in 4 seconds using 10**30). It took 11 seconds for the prime function and one second for the remainder, so < 10 million would take 100 times as long for both parts and < 10**30 would take a lifetime. When testing for primes, you only have to test up to the square root of the number, and if you store the primes found, then you can divide by the primes found, up to the highest prime found (since all the other numbers would be divisible by one of the primes), and continue using odd numbers from there to the square root. For additional help, please comment your code as some people are not familiar with the newer features, like "all", and in fact still use version 2.5 which doesn't contain "all" AFAIK.

[vegaseat]

Actually functions any() and all() where introduced with the advent of Python 2.5. Here is a little test ...

# Guido proposed boolean functions any() and all() for Python25
# and higher, tested with PortablePython 2.5.4

# combine with generator expressions like this ...
seq = (11, 23, 45)
# True if any elements of seq are > 42
print( any(x > 42 for x in seq) )
# True if all elements of seq are nonzero  
print( all(x != 0 for x in seq) )

[TrustyTony]

Interesting alternative to

>>> filter(lambda x:x>42,seq) != () ## any number in seq is over 42
True
>>> filter(lambda x:x<11,seq) != () ## any number in seq is less than 11
False
>>> filter(lambda x:x<12,seq) != () ## any number in seq is less than 12
True
>>> filter(lambda x:x<12,seq) ## this is it
(11,)
>>>