6: is_prime


#1

Boa tarde,
Será que alguém me pode ajudar?
def is_prime(x):
if x<2:
return False
if x==2:
return True
else:
for n in range(2,(x-1)):
if x%n==0:
return False
else:
return True

Porque é que este último “else” não funciona (p.e. is_prime(3)). Porque é que tem de ser:
def is_prime(x):
if x<2:
return False
if x==2:
return True
else:
for n in range(2,(x-1)):
if x%n==0:
return False

return True

Obrigado!!!


#2

Consider the following brute force approach…

Considere a seguinte abordagem de força bruta …

def is_prime(x):
    if x < 2: return False
    for n in range(2, x):
        if x % n == 0: return False
    return True

That pretty much follows the instructions to the letter.

Isso segue muito bem as instruções à carta.

We can revise it slightly…

Podemos revisá-lo um pouco …

def is_prime(x):
    if x < 2: return False
    for n in range(2, int(x / 2) + 1):
        if x % n == 0: return False
    return True

No point in iterating past the half way mark. Nothing larger than one-half of a number can be divided into it.

Nenhum ponto em iterar passado a meio caminho marca. Nada maior que a metade de um número pode ser dividido nela.

And when we consider that the lower of two factors is all we need to test for primeness, this will also give correct results:

E quando consideramos que o menor de dois fatores é tudo o que precisamos testar para a primiedade, isso também dará resultados corretos:

def is_prime(x):
    if x < 2: return False
    for n in range(2, int(x ** 0.5) + 1):
        if x % n == 0: return False
    return True
test 0..100
>>> for i in range(101):
	print (i, is_prime(i))

	
0 False
1 False
2 True
3 True
4 False
5 True
6 False
7 True
8 False
9 False
10 False
11 True
12 False
13 True
14 False
15 False
16 False
17 True
18 False
19 True
20 False
21 False
22 False
23 True
24 False
25 False
26 False
27 False
28 False
29 True
30 False
31 True
32 False
33 False
34 False
35 False
36 False
37 True
38 False
39 False
40 False
41 True
42 False
43 True
44 False
45 False
46 False
47 True
48 False
49 False
50 False
51 False
52 False
53 True
54 False
55 False
56 False
57 False
58 False
59 True
60 False
61 True
62 False
63 False
64 False
65 False
66 False
67 True
68 False
69 False
70 False
71 True
72 False
73 True
74 False
75 False
76 False
77 False
78 False
79 True
80 False
81 False
82 False
83 True
84 False
85 False
86 False
87 False
88 False
89 True
90 False
91 False
92 False
93 False
94 False
95 False
96 False
97 True
98 False
99 False
100 False
>>>