SPOJ тот же алгоритм, принятый в C, Ограничение по времени Превышено в Python

Я пытаюсь решить проблему FCTRL из SPOJ. Проблема заключается в том, чтобы найти число конечных нулей в N! для некоторых Т-тестов.

T ~ 1,00,000.
1 <= N <= 1000000000

Моя проблема очень странная. Если я попробую следующий код C, он будет принят с временем 0,22 секунды и объемом памяти 1,6 М. Но если я отправлю эквивалентный код Python 3, он говорит, что ограничение времени превысило использование памяти 11M.

C Код:

#include <stdio.h>
void fact_zeros(long int);
int main(void) {
 long int i,t,n;
 if (scanf("%ld",&t) > 0) {
 for (i=1;i<=t;i++) {
 if (scanf("%ld",&n) > 0) {
 fact_zeros(n);
 }
 }
 }
 return 0;
}
void fact_zeros(long int N) {
 long int zeros = 0;
 while (N>0) {
 N = N / 5;
 zeros += N;
 }
 printf("%ld\n",zeros);
}
</stdio.h>

Код Python 3:

"""
spoj11Factorial.py
This program calculates the number of zeroes at the 
end of the factorial of each number of the test case.
"""
def fact_zeroes( n ):
 count_5s = 0
 while (n > 0):
 n = n // 5
 count_5s += n
 return count_5s
T = int( input() )
while (T):
 T -= 1
 n = int( input() )
 zeroes = fact_zeroes( n )
 print( zeroes )

Кто-нибудь может указать, что я/что делаю в коде Python. Он работает для всех заданных тестовых случаев на моей машине.

Спасибо.

EDIT: Технические характеристики проблемы:

Added by: Adrian Kosowski
Date: 2004-05-09
Time limit: 6s
Source limit: 50000B
Memory limit: 256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages: All except: NODEJS PERL 6
Resource: ACM Central European Programming Contest, Prague 2000
1 ответ

Один очень простой способ удвоить скорость этой программы - преобразовать:

n = int( input() )

к

n = int( raw_input() )

Обратите внимание, что raw_input() возвращает строку из ввода, а input() запускает интерпретатор Python в строке после прочтения.

На моем компьютере с использованием Python 2.7 это сокращает время от 1,6 секунды до 0,7 секунды

licensed under cc by-sa 3.0 with attribution.