Problem:


Score : 300 points

Problem Statement

Given is a positive integer N.
How many tuples (A,B,C) of positive integers satisfy A \times B + C = N?

Constraints

 2 \leq N \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

3

Sample Output 1

3

There are 3 tuples of integers that satisfy A \times B + C = 3: (A, B, C) = (1, 1, 2), (1, 2, 1), (2, 1, 1).

Sample Input 2

100

Sample Output 2

473

Sample Input 3

1000000

Sample Output 3

13969985



Sample input:
3


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n = I()
ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(1, int(i**0.5)+1):
        if i % j == 0:
            cnt += 1
            if j != i // j:
                cnt += 1
    ans += cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,750000,800000,825000,850000,875000,900000,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,10261678,10997400,11366472,11736253,12106789,12478098,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])

Submission status: Time Limit Exceeded

Solution code:
import os,sys

count=0
n=int(input())

for a in range(1,n+1):
    i = n-a
    for b in range(1,i+1):
        if a*b<=n-1:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:

import math as mt 

n=int(input())
MAXN=n+1

from math import sqrt
spf = [0 for i in range(MAXN)] 

def sieve(): 
	spf[1] = 1
	for i in range(2, MAXN): 
		
	 
		spf[i] = i 

	
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
		
		# checking if i is prime 
		if (spf[i] == i): 
			
			
			for j in range(i * i, MAXN, i): 
				
			
				if (spf[j] == j): 
					spf[j] = i 

from collections import Counter
def getFactorization(x): 
	ret=Counter()
	while (x != 1): 
		ret[spf[x]]+=1 
		x = x // spf[x] 

	return ret 

sieve()
f=[1,1,2]

for i in range(3,n+1):
  c=getFactorization(i)
  ans=1
  for v in c:
    ans*=(c[v]+1)
  f.append(ans)
#print(f[:10])

total=0
for c in range(1,n):
  ans=0
  value=n-c
  factor=f[value]
  if factor==1:
    ans+=1
  
  elif factor&1:
    ans+=(factor//2)
    s=int(sqrt(value))
    ans*=2
    if s*s==value:
      ans+=1
   
  else:
    ans+=factor//2
    ans*=2
  total+=ans
  #print(ans)
print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
count=0
for i in range(1,N):
  for j in range(1,int(math.sqrt(i))+1):
    if i%j==0:
      count+=1
      if i!=j**2:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

def make_prime_list_2(num):
    if num < 2:
        return []

    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

P = make_prime_list_2(math.floor(math.sqrt(N)))
def div(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        divisor_num = 1
        for prime in P:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

ans = 0
for c in range(1, N):
    ans += div(N-c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
count = 0
for i in range(1, n):
    for j in range(1, n):
        for k in range(1, n):
            if ((i*j)+k) == n:
                count += 1
                continue
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 0
for c in range(1, n):
   x = n - c
   for b in range(1, x+1):
      if x == 1:
         ans += 1
         break
      y = x % b
      if y == 0:
         a = x // b
         if a < b:
            break
         elif a == b:
            ans += 1
         else:
            ans += 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
print(sum([i * j + k == N for i in range(1,N)for j in range(1,N)for k in range(1,N)]))

Submission status: Time Limit Exceeded

Solution code:
sols = []
from math import ceil

sol = 0

for num in range(1, 1000001):
    root = num ** (1 / 2)
    if root - int(root) == 0:
        sol += 1
    for a in range(1, ceil(root)):
        if num % a == 0:
            sol += 2
            
    sols.append([num, sol])
busca = int(input())
print(sols[busca - 2][1])

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
count = 0
for i in range(1,num+1):
  if i != num:
    for j in range(1,num+1):
      if j != num:
        for k in range(1,num+1):
          if i*j+k== num:
            count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
count=0
for a in range(1,N):
  b=1
  for b in range(1,N//a+1):
    c=N-a*b
    if c>0:
      count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 0
c = 0
for a in range (1,n):
  for b in range (1,n):
    c = n - (a * b)
    if c > 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr



nn=int(input())
ans=0

sosuu=get_sieve_of_eratosthenes(nn)
#print(sosuu)

for i in range(nn-2):
    c=i+1
    if nn-c in sosuu :
        ans1=2
    else:
        k=factorization(nn-c)
        ans1=1
        for j in range(len(k)) :
            ans1=ans1*(k[j][1]+1)

    ans=ans+ans1


ans=ans+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
count = 0
for i in range(1, n):
    for j in range(1, n):
        for k in range(1, n):
            if (i*j+k) == n:
                count += 1
                break
print(count)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return False
    return True


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


N = int(input())

res = 0
for c in range(1, N):
    ab = N - c

    if ab == 1:
        res += 1
    elif is_prime(ab):
        res += 2
    else:
        res += len(make_divisors(ab))

print(res)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,750000,800000,825000,850000,875000,900000,925000,950000,975000,1000000]
datas = [0,23,473,7053,93643,1166714, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,10261678,10997400,11366472,11736253,12106789,12478098,12850013,13222660,13595947,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
  
def make_divisors(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

res=0
for i in range(1,N):
  res+=make_divisors(i)  
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
count = 0
for i in range(1, n):
    for j in range(1, n):
        for k in range(1, n):
            if (i*j+k) == n:
                count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
count = 0
def make_divisors(n):
    count = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            count += 1
            if i != n // i:
                count += 1
    return count
for X in range(N):
  count += make_divisors(X)
print(count)

Submission status: Time Limit Exceeded

Solution code:
#C

# 与えられた数字までの数字の約数をカウントする。
def make_divisors(n):
    if n > 360000:
      count = 4661355
      i = 600
      while i*i <= n:
          if n % i == 0:
              count += 1
              if i != n // i:
                  count += 1
          i += 1
      return count
    else:
      count = 0
      i = 1
      while i*i <= n:
          if n % i == 0:
              count += 1
              if i != n // i:
                  count += 1
          i += 1
      return count


N = int(input())
counter = 0
for i in range(1,N):
  counter += make_divisors(i)

print(counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans_len = 0
for a in range(1,N):
  for b in range(1,N):
    if a*b <N:
      ans_len += 1
print(ans_len)

Submission status: Time Limit Exceeded

Solution code:
def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table
  
n = int(input())
ans = 0


for c in range(1,n):
    ab = n - c
    ans += num_divisors_table(ab)[-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x=0
for i in range(0,N):
    for j in range(1,i+1):
        if i%j==0:
            x=x+1
print(x)

Submission status: Time Limit Exceeded

Solution code:

import math as mt 

MAXN = 10**6+1


spf = [0 for i in range(MAXN)] 

def sieve(): 
	spf[1] = 1
	for i in range(2, MAXN): 
		
	 
		spf[i] = i 

	
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
		
		# checking if i is prime 
		if (spf[i] == i): 
			
			
			for j in range(i * i, MAXN, i): 
				
			
				if (spf[j] == j): 
					spf[j] = i 

from collections import Counter
def getFactorization(x): 
	ret=Counter()
	while (x != 1): 
		ret[spf[x]]+=1 
		x = x // spf[x] 

	return ret 

sieve()
f=[1,1,2]
n=int(input())
for i in range(3,n):
  c=getFactorization(i)
  ans=1
  for v in c:
    ans*=(c[v]+1)
  f.append(ans)
#print(f[:10])
from math import sqrt
total=0
for c in range(1,n):
  ans=0
  value=n-c
  factor=f[value]
  if factor==1:
    ans+=1
  
  elif factor&1:
    ans+=(factor//2)
    s=int(sqrt(value))
    ans*=2
    if s*s==value:
      ans+=1
   
  else:
    ans+=factor//2
    ans*=2
  total+=ans
  #print(ans)
print(total)

Submission status: Time Limit Exceeded

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


N = int(input())
ans = 0
for i in range(1, N):
    le = prime_factorize(N - i)
    if len(le) == len(set(le)):
        ans += pow(2, len(le))
    else:
        w = []
        p = 1
        for x in set(le):
            if le.count(x) > 1:
                w.append(x)
                p *= le.count(x) + 1
        ans += pow(2, len(set(le)) - len(w))*p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
@jit
def main():
  n=int(input())
  ans=0
  for c in range(1,n):
    k=int((n-c)**(1/2))
    for a in range(1,k+1):
      if (n-c)%a==0:
        if a**2==n-c:
          ans+=1
        else:
          ans=ans+2
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return len(lower_divisors + upper_divisors[::-1])

x=0
for c in range(1,N):
    x+=make_divisors(N-c)
print(x)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,750000,800000,850000,900000,925000,950000,975000,1000000]
datas = [0,23,473,7053,93643,1166714, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,10261678,10997400,11736253,12478098,12850013,13222660,13595947,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())

ans = 0

for i in range(1, n):
  ans += len(make_divisors(n - i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:


if __name__ == "__main__":
    N = int(input())
    C = N
    cnt = 0
    for c in range(1,C):
        A = N-c
        for a in range(1, A+1):
            B = (N-c)%a
            if B == 0:
                cnt += 1
            else:
                pass
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    ans = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans +=1
            if i != n // i:
                ans+=1

    return ans

N = int(input())
ans = 0
for c in range(1,N):
    x = N-c
    ans += make_divisors(x)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c = 1
b = 1
count = 0
while (n-c) > b:
    for a in range(n - c):
        b = (n-c) / (a+1)
        if b.is_integer():
            count += 1
    c += 1
print(count+1)

Submission status: Time Limit Exceeded

Solution code:
def f(N):
  i=2
  ans=dict()
  div_sum=1
  n=N
  while i*i <=N:
    while n%i==0:
      n=n//i
      if i in ans:
        ans[i]+=1
      else:
        ans[i]=1
    i+=1
  if n!=1:
    ans[n]=1
  ans_list=list(ans.items())
  for j in ans_list:
    div_sum*=j[1]+1
  return div_sum


N = int(input())
 
ans = 0
for C in range(1,N):
  ans += f(N-C)
  C += 1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
divList = [0]*N
 
def make_prime_list_2(num):
    if num < 2:
        return []
 
    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)
 
    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break
 
        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0
 
    return [prime for prime in prime_list if prime != 0]
  
def make_divisors(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)
 
        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count
 
        if num != 1:
            divisor_num *= 2
 
        return divisor_num
 
res=0
for i in range(1,N):
  res+=make_divisors(i)  
print(res)

Submission status: Time Limit Exceeded

Solution code:
import math



def make_seki(n):
    a = 0
    i, j = 0, 0
    for i in range(1, int(math.sqrt(n))+1, 1):
        for j in range(n, int(math.sqrt(n)-1), -1):
            if (i)*(j) == n:
                a = a+1
    
    if int(math.sqrt(n))*int(math.sqrt(n))==n:
        return a*2-1
    else:
        return a*2
        
        
from collections import defaultdict


    

n=int(input())
p=0

for i in range(1, n):
    a = n-(i)
    p = p+ (make_seki(a))
    
print(p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m = 2
z = 0

for i in range(n-2):
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

        if arr==[]:
            arr.append([m, 1])

        return arr

    x = 0
    y = 1

    r = factorization(m)
    l = len(r)

    for i in range(l):
        y = y * (r[x][1]+1)
        x+=1

    m+=1
    z = z + y

print(z+1)

Submission status: Time Limit Exceeded

Solution code:
from math import prod, floor, sqrt

N = int(input())

M = floor(sqrt(N)) 
primes = [*range(2, M+1)]
spf = [None] * 2 + [*range(2, M+1)]
for d in range(2, floor(sqrt(M))+1):
  new_primes = [] 
  for x in primes:
    if x % d == 0 and x != d:
      spf[x] = d
    else:
      new_primes.append(x)
  primes = new_primes
  #primes = [x for x in primes if x % d or x == d]

def divide(x): # x > 1
  soin = []
  old_spf = None
  while x > 1:
    if x > M:
      for p in primes:
        if x % p == 0:
          new_spf = p
          break
      else:
        new_spf = x
    else:
      new_spf = spf[x]
    if new_spf == old_spf:
      soin[-1] += 1
    else:
      soin.append(1)
    x = x // new_spf
    old_spf = new_spf
  return prod(i+1 for i in soin)

print(1 + sum(divide(x) for x in range(2, N)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def yakusu(n):
  S = {1, n}
  for j in range(2, int(n ** 0.5) + 1):
    if n % j == 0:
      S.add(j)
      S.add(n // j)
  return len(S)

print(sum([yakusu(i) for i in range(2, N)]) + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# c = N-1
# tmp = [0]*N
ans = 0
# def make_divisors(n):
#     lower_divisors , upper_divisors = [], []
#     i = 1
#     while i*i <= n:
#         if n % i == 0:
#             lower_divisors.append(i)
#             if i != n // i:
#                 upper_divisors.append(n//i)
#         i += 1
#     return lower_divisors + upper_divisors[::-1]
#
# for i in range(1,N):
#     tmp[i] = len(make_divisors(i))
#
# print(sum(tmp))
A = 1
B = 1
while(A < N):
    while(A*B<N):
        ans += 1
        B += 1
    B = 1
    A += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
def A(n):
    counter=0
    for i in range(1,n+1):
        if n%i==0:
            counter+=1
    return counter

counter=0
for i in range(1,N):
    counter+=A(i)
print(counter)

Submission status: Time Limit Exceeded

Solution code:

import math as mt 

MAXN = 10**6+1


spf = [0 for i in range(MAXN)] 

def sieve(): 
	spf[1] = 1
	for i in range(2, MAXN): 
		
	 
		spf[i] = i 

	
	for i in range(4, MAXN, 2): 
		spf[i] = 2

	for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
		
		# checking if i is prime 
		if (spf[i] == i): 
			
			
			for j in range(i * i, MAXN, i): 
				
			
				if (spf[j] == j): 
					spf[j] = i 

from collections import Counter
def getFactorization(x): 
	ret=Counter()
	while (x != 1): 
		ret[spf[x]]+=1 
		x = x // spf[x] 

	return ret 

sieve()
f=[1,1,2]
for i in range(3,10**6):
  c=getFactorization(i)
  ans=1
  for v in c:
    ans*=(c[v]+1)
  f.append(ans)
#print(f[:10])
from math import sqrt
n=int(input())
total=0
for c in range(1,n):
  ans=0
  value=n-c
  factor=f[value]
  if factor==1:
    ans+=1
  
  elif factor&1:
    ans+=(factor//2)
    s=int(sqrt(value))
    ans*=2
    if s*s==value:
      ans+=1
   
  else:
    ans+=factor//2
    ans*=2
  total+=ans
  #print(ans)
print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
divList = [0]*N

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
  
def make_divisors(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

res=0
for i in range(1,N):
  res+=make_divisors(i)  
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
count = 0
if N < 100:
    for i in range(1,N):
        for j in range(1,N):
            for k in range(1,N):
                if i*j + k == N:
                    count += 1
else:
    for i in range(1,N):
        for j in range(1,N//i+1):
            c = N - i*j
            if 1 <= c <= N:
                count += 1 
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
ans = 0

for a, b in itertools.product(range(1,N), range(1,N)):
    c = N-a*b
    if c > 0 and a*b+c == N:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
count=0


def div(n):
    c = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            c+=1
            if i != n // i:
                c+=1

    return c

for i in range(1,n):
    l = div(i)
    if l%2==1:
        count+=1+(l//2)*2
    else:
        count+=l

print(count)

Submission status: Time Limit Exceeded

Solution code:
def factorization(n):
    arr = []
    temp = n
    c = 1
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
            c = c * (cnt + 1)

    if temp != 1:
        arr.append([temp, 1])
        c = c * (1 + 1)

    if arr == []:
        arr.append([n, 1])
        c = c * (1 + 1)

    return c


n = int(input())
ans = 0
for i in range(1, n):
    ans += factorization(n - i)
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = 1
total = 0

def makedivs(n):
      divs = 0
      i = 1
      while(i*i <= n):
            if n % i == 0:
                  divs += 1
                  if i*i != n:
                        divs += 1
            i += 1
      return divs
                  

while(N-c >= 1):
      divnums = makedivs(N-c)
      total += divnums
      c += 1
      
print(total)

Submission status: Time Limit Exceeded

Solution code:

def divisor(n): 
    cnt=0
    i = 1
    while i**2 <= n:
        if n%i == 0:
            if i==n//i:
                cnt+=1
            else:
                cnt+=2
        i += 1
    return cnt


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input(''))
result=0
for c in range(1,n):
    n2 = n-c
#    div = divisor(n2)
#    print("{}->{}".format(n2,div))
    fact = make_divisors(n2)
#    print(fact)
    result+=len(fact)

print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
c=1
b=1
while n-c!=0:
	c+=1
	while n-c-b!=0:
		b+=1
		if (n-c)%b==0:
			ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def cnt(n):
    count = 0
    for i1 in range(1,n):
        for i2 in range(1,n):
            for i3 in range(1,n):
                if i1 * i2 + i3 == n:
                    count += 1
            
    return count

cnt = cnt(int(input()))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []#ソートしなくても小さい順になる工夫
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
ans=0
for c in range(1,n):
    for a in make_divisors(n-c):
            b=(n-c)//a
            if b<a:
                break
            ans+=1
            if a!=b:
                ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
cnt = 0
for a in range(1, N):
    for b in range(1, N):
        if a * b < N:
            cnt += 1
        
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = 0
count = 0

for c in range(1,n+1):
  for b in range(1,(n+1)-c):
    if (n-c) % b == 0: 
      count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 200000, 250000,300000,350000, 400000,450000, 500000,600000,675000,750000,800000,850000,900000,925000,950000,975000,1000000]
datas = [0,23,473,7053,93643,1166714, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,8075420,9164377,10261678,10997400,11736253,12478098,12850013,13222660,13595947,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])

Submission status: Time Limit Exceeded

Solution code:
def count_divisors(n):
    counter = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            if i == n / i:
                counter += 1
            else:
                counter += 2
        i += 1
    return counter


counter = 0
N = int(input())

for i in range(1, N):
    counter += count_divisors(N - i)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

count = 0
for A in range(1, N):
  for B in range ((A + 1), N):
    if (A*B) < N:
      count += 1

count = count * 2

for x in range(1, N):
  if x**2 < N:
    count += 1

print(count)