Problem p02900 (python)

Fixed submission:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a


import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

def prime_num(target):
    ra = 2
    prime = 0
    while target>1:
        if target%ra == 0:
            prime += 1
            while target%ra==0:
                target = target//ra
            if is_prime(target):
                prime += 1
                break
        if ra == 2:
            ra += 1
        else:
            ra += 2
    return prime   
        
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = prime_num(gcd)    
    print(ans+1)

Buggy submission (verdict: Runtime Error):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = math.ceil(math.sqrt(target))
    target_list = [i for i in range(2, dest//2+1) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = target_list[0]
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num

import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

Buggy submission (verdict: Runtime Error):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a
 
#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = math.ceil(math.sqrt(target))
    target_list = [i for i in range(2, dest+2) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = target_list[0]
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num
 
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

Buggy submission (verdict: Runtime Error):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a
 
#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, dest+2) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num   
 
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

Buggy submission (verdict: Runtime Error):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a
 
#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, dest+1) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num   
 
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)

Buggy submission (verdict: Runtime Error):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

import math
import numpy as np
def primes_num(target):
    dest = int(math.sqrt(target))
    datas = np.array([i for i in range(2, target)], dtype="object")
    mask = target%datas == 0
    prime_num = 0
    while True:
        num_min = np.min(datas[mask])
        if num_min > dest:
            prime_num += len(datas[mask])
            break
        prime_num += 1
        mask[num_min-2::num_min] = False
        if True in mask:
            pass
        else:
            break
    return prime_num
    
    

a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    ans = primes_num(gcd)    
    print(ans+1)

Buggy submission (verdict: Runtime Error):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

#targetまでの素数の数
import math
def sieve_of_eratosthenes(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, target+1)]
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)        
        target_list = [i for i in target_list if i%num_min!=0]
 
    return prime_list

def sieve_of_eratosthenes2(target):
    dest = int(math.sqrt(target))
    target_list = [i for i in range(2, target+1) if target%i==0]
    prime_list = []
 
    while True:
        num_min = min(target_list)
        if num_min > dest:
            prime_list.extend(target_list)
            break
        prime_list.append(num_min)        
        target_list = [i for i in target_list if i%num_min!=0]
 
    return prime_list


a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
else:
    lis = sieve_of_eratosthenes2(gcd)
    ans = len(lis) + 1
    print(ans)