As suggested by our professor, I'd like to share challenges and showcase programs too. But do bear with my primitive codes as I've never programmed (I'm talking about computer programming) before coming to IISER, so please suggest things as you can help me and others learn...
Thank you
Hi everyone... I think many of you have heard about Caesar Ciphers. If not, google them and it's one of the most basic ciphers (you might have used it without knowing its name).
I wrote a program by using basic modular arithmetic and ASCII values to code and decode Caesar ciphers.
The code is as follows...
................................................................................................................................................................................
print("Welcome to Caesar Coder and Decoder...")
print("For brute force, shift value = 0")
a = int(input("Shift value:"))
b = raw_input("Encrypted/Decrypted message:")
c = list(b)
p = []
print("")
if a != 0:
for x in range(0,len(b)):
d = ord(c[x]) + a
if ord(c[x]) > 64 and ord(c[x]) < 91:
p.append(chr(((d - 39) % 26) + 65))
elif ord(c[x]) > 96 and ord(c[x]) < 123:
p.append(chr(((d - 71) % 26) + 97))
else:
p.append(c[x])
q = "".join(p)
print(q)
elif a ==0:
for y in range(0,27):
for x in range(0,len(b)):
d = ord(c[x]) + y
if ord(c[x]) > 64 and ord(c[x]) < 91:
p.append(chr(((d - 39) % 26) + 65))
elif ord(c[x]) > 96 and ord(c[x]) < 123:
p.append(chr(((d - 71) % 26) + 97))
else:
p.append(c[x])
q = "".join(p)
print(q)
print("")
p = []
.................................................................................................................................................................................
A python file is attached of the same.
Hi everyone...
Have you heard of Emirps? They are prime numbers who are primes even backwards (eg. 13,31).
The following program is to print a list of emirps. Try to write a program for it. I'll share my program.
..............................................................................................................................................................................
def prim(x):
k=0
for a in range(2,x):
if x % a == 0:
k = 1
break
if k == 0:
return 1
else:
return 0
p = input("Emirps till:")
l = []
for x in range(2,p):
y=str(x)
if (prim(x) == 1) and (prim(int(y[::-1])))==1 and (y != y[::-1]):
l.append(x)
print(l)
................................................................................................................................................................................
A python file is attached of the same.
Good one Sourav. Keep it up.
I again emphasize the need of readable codes. I would appreciate if students add comments in code to make them more transparent and readable. I am reorganizing Sourav's code to make it more readable.
def isprime(n): # This function returns True if n is prime, else returns False.
count = 0 # Idea is to count number of divisors.
for i in range(1,n+1):
if n%i == 0:
count = count+1
if count == 2:
return True
else:
return False
def backwards(n): # This function inverts an integer. Ex. backwards(235) = 532.
s = str(n)
return int(s[::-1])
# Ask user for the integer upto which emirps are to be printed.
n = input("I wish to find emirps upto : ")
for m in range(1,n+1): # Upto n check the conditions for being emrip and print.
if isprime(m) and isprime(backwards(m)) and m != backwards(m):
print m,
Second step should be to make program more efficient. So where all can we improve?
Keep Pythoning!
In the present logic, we find all the divisors till N by iterating I over all 1 to n and checking if N is divisible by I. If I is divisible, COUNT is incremented by 1. Then COUNT is checked if it is = 2, and if so, it is a prime. I intend to make this process more efficient by providing two different methods, one by reducing the number of checks required, and the other by not requiring to count the divisors at all.
Method 1-
We assume the following: for any natural number x which is a divisor of N, there exists another y such that xy=N.
What this means is that for any divisor of N, there exists another divisor, whose product with the former is equal to N, i.e. divisors come in pairs.
Hence, when we find one of the divisors, the other one can be conveniently found by simply dividing N by that divisor. Further, this also means that we need to run that loop only till sqrt(N). (Think why this is so)
But what about numbers which are NOT perfect square? We can not run the loop for a non integer number of times can we? So we find the greatest integer smaller than the root of the number by using a function called floor(). Each time we encounter a divisor, we simply increment COUNT by 2 instead of 1.
However, if N is a proper square, then the number of divisors given by the function will be greater than the actual by 1 (Why?). So we simply check if the number is a perfect square(How? Hint: use floor()) and reduce the number of divisors by 1. Then we check if COUNT==2 and return True or False accordingly.
Method 2-
We assume the following: A number with even one divisor (not equal to 1 or itself) will NOT be a prime. The proof of assumption is self-evident by definition of prime.
Since we know that if we find EVEN ONE divisor in 2 to sqrt(N), the number is not prime, we can skip checking for other divisors the moment we find a divisor. This can be implemented by using the fact that the return statement IMMEDIATELY stops the function. If we iterate through the complete loop and still don't find a divisor, we can simply return that it is True.
ANALYSIS-
Now that we have three different ways (essentially only 2), let us analyse these to see which is the fastest.
Comparing the method given by Sourav and Method 1, we see that Method 1 has root n iterations whereas the former has n iterations. Hence, Method 1 is faster.
Comparing Method 1 and Method 2, we see that in the scenario that N is a prime number, both have equal number of iterations (sqrt N). But in the case of a Composite number, Method 2 runs only till it finds the first divisor and stops there, whereas Method 1 continues to loop. Further in Method 1, we required a COUNT variable which was not required in Method 2, making Method 2 more space efficient too. I have NOT provided the implementation of the above Methods to give you an opportunity to do so yourself.
Further Reading-
Good work Dhruva. Now, following your suggestion, I am modifying my code a bit.
def isprime(n): # This function returns True if n is prime, else returns False.
count = 1 # Since 1 divides each n, that is the first divisor.
d = 2 # We look for next divisor d > 1.
# The next divisor equals n if and only if n is prime.
while count == 1:
if n%d == 0:
count = count + 1
d = d + 1
if d == n + 1:
return True
else:
return False
Now, to make it even more efficient I could have stopped if count == 1 and d > sqrt(n). A priori it is a good idea. Though one must estimate the "cost" that we need to pay in order to extract or "buy" this square root. How much do pay in terms of time and space is a deep question that we won't discuss in this course.
Nevertheless, I will be extremely satisfied to see if someone could incorporate this suggestion of Dhruva.
And interesting thing would be to compare time all these codes take in order to produce lists of primes, upto, say, 1,00,000. Lets do that. But, how? Just see this link at stackoverflow.
Keep Pythoning!
The time required to find the root completely skipped my mind. Will try to profile the code and let you know the results.
You don't need to calculate the square root. To know whether a number k is smaller than sqrt(n), you only need to calculate l=n//k and check whether l>k or not.
This can also be expensive if you need to do it for every k. However, in the given program, you can also use l*k=n to check whether k divides n.
Write a program using this method to check primality.
Doing some runs, these are the results:
Laptop 1:
Run with Sqr Root method:
7.022799
7.507611
7.100540
7.047137
7.039505
Run with n/2 method:
All over 20 secs
Laptop 2:
Run with Sqrt method:
10.317666
12.388034
11.959374
13.191719
12.795440
Run with n/2 method:
All over 20 secs
Reason:
The sqrt method is faster than the n/2 method, especially larger numbers. For example, if n=10^6, the sqrt method loops 1000 times, whereas the n/2 method runs 5*10^5 times, which is 500 times longer. This easily offsets the overhead of having to calculate the sqrt of n. Hence, for larger values, sqrt method should be preferred over the n/2 method. Looking at the time complexity of the sqrt function, n=7 is the largest value for n/2 being faster than sqrt(n).
Code i used for the analysis-
import math
import time
def isprime(n):
i=2
sq=math.floor(math.sqrt(n))
while i <= sq:
if n%i==0:
return False
i+=1
return True
start_time = time.clock()
n=2
while (n <=1000000):
isprime(n)
n+=1
print time.clock()-start_time
import math
import time
def isprime(n):
i=2
nby2=n/2
while i <= nby2:
if n%i==0:
return False
i+=1
return True
start_time = time.clock()
n=2
while (n <=1000000):
isprime(n)
n+=1
print time.clock()-start_time
Good Dhruva. So, now It seems buying square roots from Python is not a bad deal.
I am starting a new thread on interesting primality tests. Someone should try to code in Python.