I recently began to learn Python and encountered this problem.
The condition:
You and your friends are playing the next game. Friends write 𝑁 natural numbers in a row on the board. Your task is to find as many consecutive numbers as possible that are divisible by the same number greater than 1. Since it is difficult to find the answer manually, you decided to write a program that will do the job for you.
Input:
The first line of the input contains the number 𝑁 (1 ≤ 𝑁 ≤ 100000). The second line is separated by a space 𝑁 integers 𝐴1...𝐴 𝑁(1 ≤ 𝐴𝑖 ≤ 1000, 1 ≤ 𝑖 ≤ 𝑁). These are the numbers that your friends wrote. They are given in the same order as they are placed on the board.
Output:
Your program should output a single integer — the largest number of consecutive numbers in a given sequence that would be divisible by the same natural number greater than 1.
Here is my code:
Python from math import gcd def func(n,a): mx = 0 for i, cur_g in enumerate(a): if n - i < mx: break p = 0 for j in range(i, n): cur_g = gcd(cur_g, a[j]) if cur_g == 1: break p += 1 if mx < p: mx = p return mx print(func(int(input()), [int(i) for i in input().split()])) The problem is that I can't pass the time check: the program runs for longer than 0.5 seconds. And I can't think of any way to speed up the program. It may even be necessary to solve the problem itself in a different way. Please help me. Thanks in advance!
