Problem p02574 (python)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

#エラストテネスのふるい
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve

#高速素因数分解
def fast_factorization(n, sieve):
  prime={}
  while n>1:
    p=sieve[n]
    #nが素数の場合
    if p==0:
      prime[n]=prime.get(n,0)+1
      break
    #nが素数ではない場合
    else:
      prime[p]=prime.get(p,0)+1
      n=n//p
  return prime

check=set()
if setwise_coprime(a)==1:
  #素因数のダブリをcheck
  sieve=create_sieve(10**6)
  for i in range(n):
    if a[i]!=1:
      s=fast_factorization(a[i], sieve)
      for i in s:
        if i in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(i)
  print("pairwise coprime")    
else:
  print("not coprime")

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

check=set()

if setwise_coprime(a)==1:
  s=erast(1000)
  s.sort()
  for i in range(n):
    flg=0
    if a[i]!=1:
      for j in range():
        if a[i]%s[j]==0:
          flg=1
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
      if flg==0:
        if a[i] in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(a[i])
  print("pairwise coprime")    
else:
  print("not coprime")

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=prime_set
  return s

check=set()

if setwise_coprime(a)==1:
  s=erast(1000000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if s[j]>a[i]:
          break
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=prime_set
  return s

check=set()

if setwise_coprime(a)==1:
  s=erast(1000000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if s[j]>a[i]:
          break
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

def is_prime(n):
  if n==1:
    return False
  if n==2:
    return True
  else:
    for i in range(int(math.sqrt(n))+1):
      if n%i==0:
        return False
    return True
  
check=set()
for i in range(n):
  if is_prime(a[i]):
    check.add(a[i])
  
if setwise_coprime(a)==1:
  s=erast(1000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

def erast(n):
  num_set=set()
  prime_set=set()
  for i in range(2,n+1):
    if i not in num_set:
      prime_set.add(i)
      for j in range(i*i,n+1,i):
        num_set.add(j)
  s=list(prime_set)
  return s

def is_prime(n):
  if n==1:
    return False
  if n==2:
    return True
  else:
    for i in range(int(math.sqrt(n))+1):
      if n%i==0:
        return False:
    return True
  
check=set()
if setwise_coprime(a)==1:
  s=erast(1000000)
  s.sort()
  for i in range(n):
    if a[i]!=1:
      for j in range(len(s)):
        if a[i]%s[j]==0:
          if s[j] in check:
            print("setwise coprime")
            sys.exit()
          else:
            check.add(s[j])
            
  print("pairwise coprime")    
else:
  print("not coprime")