Finding Square roots

Average method

find $\sqrt{\alpha}$ where $\alpha$ is a real positive number

In [80]:
a = 5
In [81]:
a
Out[81]:
5
In [82]:
x0 = -a**2-1
x1 = a**2+1
In [83]:
def average(x0,x1):
    return (x0+x1)/2
In [84]:
average(2,7)
Out[84]:
4.5
In [ ]:
In [86]:
low=x0
high = x1
xchecker = (a+100)**0.5
while (xchecker**2-a)**2>0.0000000001:
    xnew = average(low,high)
    if xnew**2==a:
        print("exact number: ",xnew)
        break
    elif xnew**2>a:
        high = xnew
    else:
        low = xnew
    xchecker=xnew
In [87]:
xchecker
Out[87]:
2.236067295074463
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [88]:
def find_sqrt(a,low,high):
    xchecker = (a+10)**0.5
    while (xchecker**2-a)**2>0.0000000001:
        xnew = average(low,high)
        if xnew**2==a:
            print("exact number: ",xnew)
            break
        elif xnew**2>a:
            high = xnew
        else:
            low = xnew
        xchecker=xnew
        
    return xnew
In [89]:
find_sqrt(30,0,20)
Out[89]:
5.4772257804870605
In [94]:
find_sqrt(100,-20,20)

exact number:  10.0
Out[94]:
10.0
In [ ]:
In [85]:
for count in range(0,20):
    print(count)
    if count>10:
        break

0
1
2
3
4
5
6
7
8
9
10
11

Finding Primes

In [100]:
m = 500
In [103]:
m=121
num=m-1
while num>1:
    if m%num==0:
        print('not prime:',num)
        break
    else:
        num-=1

not prime: 11
In [102]:
111/37
Out[102]:
3.0
In [104]:
def Check_prime(x):
    num=x-1
    ans= "prime"
    while num>1:
        if x%num==0:
            ans="not prime"
            break
        else:
            num-=1
    return ans
In [111]:
Check_prime(1611)
Out[111]:
'not prime'
In [114]:
def Check_prime(x):
    num=x-1
    ans= True
    while num>1:
        if x%num==0:
            ans=False
            break
        else:
            num-=1
    return ans
In [116]:
Check_prime(13)
Out[116]:
True
In [117]:
m = 500
for count in range(2,m):
    if Check_prime(count):
        print('PRIME: ',count)
        

PRIME:  2
PRIME:  3
PRIME:  5
PRIME:  7
PRIME:  11
PRIME:  13
PRIME:  17
PRIME:  19
PRIME:  23
PRIME:  29
PRIME:  31
PRIME:  37
PRIME:  41
PRIME:  43
PRIME:  47
PRIME:  53
PRIME:  59
PRIME:  61
PRIME:  67
PRIME:  71
PRIME:  73
PRIME:  79
PRIME:  83
PRIME:  89
PRIME:  97
PRIME:  101
PRIME:  103
PRIME:  107
PRIME:  109
PRIME:  113
PRIME:  127
PRIME:  131
PRIME:  137
PRIME:  139
PRIME:  149
PRIME:  151
PRIME:  157
PRIME:  163
PRIME:  167
PRIME:  173
PRIME:  179
PRIME:  181
PRIME:  191
PRIME:  193
PRIME:  197
PRIME:  199
PRIME:  211
PRIME:  223
PRIME:  227
PRIME:  229
PRIME:  233
PRIME:  239
PRIME:  241
PRIME:  251
PRIME:  257
PRIME:  263
PRIME:  269
PRIME:  271
PRIME:  277
PRIME:  281
PRIME:  283
PRIME:  293
PRIME:  307
PRIME:  311
PRIME:  313
PRIME:  317
PRIME:  331
PRIME:  337
PRIME:  347
PRIME:  349
PRIME:  353
PRIME:  359
PRIME:  367
PRIME:  373
PRIME:  379
PRIME:  383
PRIME:  389
PRIME:  397
PRIME:  401
PRIME:  409
PRIME:  419
PRIME:  421
PRIME:  431
PRIME:  433
PRIME:  439
PRIME:  443
PRIME:  449
PRIME:  457
PRIME:  461
PRIME:  463
PRIME:  467
PRIME:  479
PRIME:  487
PRIME:  491
PRIME:  499
In [118]:
Check_prime(13)
Out[118]:
True
In [123]:
%%time
m = 20000
Prime_list=[]
for count in range(2,m):
    if Check_prime(count):
        Prime_list.append(count)
        
print(len(Prime_list))        

2262
CPU times: user 10.3 s, sys: 92.4 ms, total: 10.4 s
Wall time: 10.5 s
In [125]:
%%time

Number = 50000
Prime_list=[2]
count=2
while count <Number:
    Prime=True
    count+=1
    for x in range(0,len(Prime_list)):
        if count%Prime_list[x]==0:
            Prime=False
            break
    if Prime:
        Prime_list.append(count)

print(len(Prime_list))

5133
CPU times: user 1.37 s, sys: 19.5 ms, total: 1.39 s
Wall time: 1.41 s

sieve method

In [140]:
Primes=[]
UpperInt = 20
Allnums = set(range(UpperInt,1,-1))
In [141]:
Allnums
Out[141]:
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
In [142]:
p=Allnums.pop()
Primes.append(p)
In [143]:
Allnums
Out[143]:
{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
In [144]:
Primes
Out[144]:
[2]
In [145]:
set(range(p*2,UpperInt+1,p))
Out[145]:
{4, 6, 8, 10, 12, 14, 16, 18, 20}
In [146]:
Allnums.difference_update(set(range(p*2,UpperInt+1,p)))
In [147]:
Allnums
Out[147]:
{3, 5, 7, 9, 11, 13, 15, 17, 19}
In [148]:
bob=range(3,20,3)
In [149]:
print([x for x in bob])

[3, 6, 9, 12, 15, 18]
In [ ]:
In [151]:
#Sieve method
UpperInt = int(input('please input your positive integer:'))
Allnums = set(range(UpperInt,1,-1))
%time
Primes=[]
while Allnums:
    p=Allnums.pop()
    Primes.append(p)
    Allnums.difference_update(set(range(p*2,UpperInt+1,p)))
#print(Primes)
print(len(Primes))

CPU times: user 2 µs, sys: 0 ns, total: 2 µs
Wall time: 4.77 µs
5133
In [154]:
%%time
UpperInt=5000000

Allnums = set(range(UpperInt,1,-1))

Primes=[]
while Allnums:
    p=Allnums.pop()
    Primes.append(p)
    Allnums.difference_update(set(range(p*2,UpperInt+1,p)))
#print(Primes)
print(len(Primes))

348533
CPU times: user 1.55 s, sys: 85.3 ms, total: 1.63 s
Wall time: 1.66 s
In [ ]: