import matplotlib.pyplot as plt
import time

# Function with constant runtime complexity: O(1)
def constant_time():
    return 42

# Function with linear runtime complexity: O(n)
def linear_time(n):
    result = 0
    for i in range(n):
        result += i
    return result

# Function with quadratic runtime complexity: O(n^2)
def quadratic_time(n):
    result = 0
    for i in range(n):
        for j in range(n):
            result += i * j
    return result

# Function with exponential runtime complexity: O(2^n)
def exponential_time(n):
    if n <= 1:
        return n
    return exponential_time(n-1) + exponential_time(n-2)

# Function to measure the execution time of a function
def measure_time(func, *args):
    start_time = time.time()
    result = func(*args)
    end_time = time.time()
    execution_time = end_time - start_time
    return execution_time

# Input sizes
input_sizes = list(range(1, 11))  # Adjust the input sizes as desired

# Measure execution times for different complexities
constant_times = [measure_time(constant_time) for _ in input_sizes]
linear_times = [measure_time(linear_time, n) for n in input_sizes]
quadratic_times = [measure_time(quadratic_time, n) for n in input_sizes]
exponential_times = [measure_time(exponential_time, n) for n in input_sizes]

# Plotting the graph
plt.plot(input_sizes, constant_times, label='O(1)')
plt.plot(input_sizes, linear_times, label='O(n)')
plt.plot(input_sizes, quadratic_times, label='O(n^2)')
plt.plot(input_sizes, exponential_times, label='O(2^n)')
plt.xlabel('Input Size (n)')
plt.ylabel('Execution Time (s)')
plt.title('Runtime Complexity Comparison')
plt.legend()
plt.show()


# Python implementation of Karatsuba algorithm for bit string multiplication.

# Helper method: given two unequal sized bit strings, converts them to
# same length by adding leading 0s in the smaller string. Returns the
# the new length
def make_equal_length(str1, str2):
	len1 = len(str1)
	len2 = len(str2)
	if len1 < len2:
		for i in range(len2 - len1):
			str1 = '0' + str1
		return len2
	elif len1 > len2:
		for i in range(len1 - len2):
			str2 = '0' + str2
	return len1 # If len1 >= len2

# The main function that adds two bit sequences and returns the addition
def add_bit_strings(first, second):
	result = "" # To store the sum bits

	# make the lengths same before adding
	length = make_equal_length(first, second)
	carry = 0 # Initialize carry

	# Add all bits one by one
	for i in range(length-1, -1, -1):
		first_bit = int(first[i])
		second_bit = int(second[i])

		# boolean expression for sum of 3 bits
		sum = (first_bit ^ second_bit ^ carry) + ord('0')

		result = chr(sum) + result

		# boolean expression for 3-bit addition
		carry = (first_bit & second_bit) | (second_bit & carry) | (first_bit & carry)

	# if overflow, then add a leading 1
	if carry:
		result = '1' + result

	return result

# A utility function to multiply single bits of strings a and b
def multiply_single_bit(a, b):
	return int(a[0]) * int(b[0])

# The main function that multiplies two bit strings X and Y and returns
# result as long integer
def multiply(X, Y):
	# Find the maximum of lengths of x and Y and make length
	# of smaller string same as that of larger string
	n = max(len(X), len(Y))
	X = X.zfill(n)
	Y = Y.zfill(n)

	# Base cases
	if n == 0: return 0
	if n == 1: return int(X[0])*int(Y[0])

	fh = n//2 # First half of string
	sh = n - fh # Second half of string

	# Find the first half and second half of first string.
	Xl = X[:fh]
	Xr = X[fh:]

	# Find the first half and second half of second string
	Yl = Y[:fh]
	Yr = Y[fh:]

	# Recursively calculate the three products of inputs of size n/2
	P1 = multiply(Xl, Yl)
	P2 = multiply(Xr, Yr)
	P3 = multiply(str(int(Xl, 2) + int(Xr, 2)), str(int(Yl, 2) + int(Yr, 2)))

	# Combine the three products to get the final result.
	return P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2

if __name__ == '__main__':
	print(multiply("1100", "1010"))
	print(multiply("110", "1010"))
	print(multiply("11", "1010"))
	print(multiply("1", "1010"))
	print(multiply("0", "1010"))
	print(multiply("111", "111"))
	print(multiply("11", "11"))


# Python 3 program to find a prime factor of composite using
# Pollard's Rho algorithm
import random
import math

# Function to calculate (base^exponent)%modulus
def modular_pow(base, exponent,modulus):

	# initialize result
	result = 1

	while (exponent > 0):

		# if y is odd, multiply base with result
		if (exponent & 1):
			result = (result * base) % modulus

		# exponent = exponent/2
		exponent = exponent >> 1

		# base = base * base
		base = (base * base) % modulus

	return result

# method to return prime divisor for n
def PollardRho( n):

	# no prime divisor for 1
	if (n == 1):
		return n

	# even number means one of the divisors is 2
	if (n % 2 == 0):
		return 2

	# we will pick from the range [2, N)
	x = (random.randint(0, 2) % (n - 2))
	y = x

	# the constant in f(x).
	# Algorithm can be re-run with a different c
	# if it throws failure for a composite.
	c = (random.randint(0, 1) % (n - 1))

	# Initialize candidate divisor (or result)
	d = 1

	# until the prime factor isn't obtained.
	# If n is prime, return n
	while (d == 1):

		# Tortoise Move: x(i+1) = f(x(i))
		x = (modular_pow(x, 2, n) + c + n)%n

		# Hare Move: y(i+1) = f(f(y(i)))
		y = (modular_pow(y, 2, n) + c + n)%n
		y = (modular_pow(y, 2, n) + c + n)%n

		# check gcd of |x-y| and n
		d = math.gcd(abs(x - y), n)

		# retry if the algorithm fails to find prime factor
		# with chosen x and c
		if (d == n):
			return PollardRho(n)

	return d

# Driver function
if __name__ == "__main__":

	n = 10967535067
	print("One of the divisors for", n , "is ",PollardRho(n))

# This code is contributed by chitranayal


rsa_250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
p*q