Hey guys, 
Hope you all are doing great. I am back with another problem of Project Euler on

Project Euler #3: Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of a given number N?
Input Format
First line contains T, the number of test cases. This is followed by T lines each containing an integer N.
Output Format
For each test case, display the largest prime factor of N.
Constraints
1≤T≤10
10≤N≤1012
Sample Input
2
10
17
Sample Output
5
17

Algorithm:


For finding prime numbers we need to check whether a number is not divisible by any number except 1 and itself.

So as a brute force it is to iterate through all numbers less than it and check of the divisibility.

But as we search for prime numbers < N, its time complexity will be
O(N^2)


Hence for large value brute force algorithm will fail.

So we can find a pattern to decrease the number of iterations:

As the first 5 prime numbers are 2, 3, 5, 7 and 11.
We can filter the multiples of these, so number of iteration will become less than half

Further,
If a number n is not a prime, it can be factored into two factors a and b:
n = a*b
If both a and b were greater than the square root of n,  a*b would be greater than n. So at least one of those factors must be less or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.
So in worst case the time complexity will be
O(n*log(n))
And Presto!! We are Done!!

Now to program this in python, you need to take care of all conditions and make it work. Here is a snippet for my submission to the problem

Program:


import math
def is_prime(num): # Here you can add condition for exclusion of multiples of 2,3,5,7 & 11
 for j in range(2,int(math.sqrt(num)+1)):
  if (num % j) == 0: 
   return False
 return True
t=input()
while(t>0):
    t=t-1;
    n=input()
    for i in range(n,2,-1):
        if(n%i==0 and is_prime(i)):
            print i
            break;
Posted by
Labels: Algorithms Hackerrank Hackerrank.com Mathematics Programming Project Euler Python
0

Add a comment

Greetings!! Here's a series of Cold Golf problems and solutions in Python as a part of 21 days of Code | Code Golf by Skillenza 

https://skillenza.com/challenge/21days-of-code

DAY - I

A Little Complex

Given n complex numbers each x + yi, where x is the real part and y is the imaginary part, find their product.

Input Format

The first line of input consists of an integer t denoting the number of test cases. t test cases follow.
1

For the need of a simple tabular Grid in your Angular JS application, one of the most basic and simple to use package is angular-ui-grid. The implementation is easy in many of the use cases, but when it comes to extend the limits of the ui-grid, life becomes tough.

One of the tricky task is to set the Grid height as dynamic, in other words to make the grid more flexible to number of rows and the grid size would depend on it.

Hey guys, Hope you all are doing great. 

Algorithm To Convert Post-fix Expression into Infix expression:-

Scan the Post-fix String from Left to Right. If the character is an Operand, then Push it on to the deque. If the character is an Operator, then Pop left Operator 1 and Operand 2 and concatenate them using Infix notation where the Operator is in between the Two Operands. The resultant expression is then pushed on the deque.

Hey guys, Hope you all are doing great.

As the first part of this series of Python package and installation we will cover pip vs Conda

pip vs Conda

pip

Python packages only. Compiles everything from source. Installs binary, wheel, the ones which pypi supply Blessed by the core Python community (i.e., Python 3.4+ includes code that automatically boostraps pip). conda

Python agnostic.

Hey guys,

Hope you all are doing great. I love Code Golfing, what it brings out in you is the hidden concepts of a programming language and especially the push to implement same thing in numerous ways.

Code Golfing and Python - Yeah that's my Poison!

Below are few tips and tricks which will give you an edge over other programmer to write the shortest code:

1. The foo if condition else bar condition can be shortened to

True if condition else False ------- [False,True][condition]

2.

Hey guys, Hope you all are doing great.

I have always found Regular expressions or REGEX quite amazing. You can solve your string related problem in just some simple magic of patterns.

Our brain works very well to identify the pattern in our day to day life. As these are visual clues, we tend to catch and analyse them better. In fact, their you make negligible mistake to tackle the scenario.
1

Hey guys, Hope you all are doing great. I am back with Some Python Programming tips for

CODE GOLF Challenges.

Here are the Second part of code golfing Tips in Python

I prefer Python or Python3 myself for code golfing

So we will discuss dome tips as generics for code golf programming in Python:

7. Use `n` to convert an integer to a string instead of using str(n).

Hey guys, Hope you all are doing great. I am back with Some Python Programming tips for

CODE GOLF Challenges.

So, What is CODE GOLF??

As per Wikipedia, it is a type of recreational computer programming competition in which participants strive to achieve the shortest possible source code (not to be confused with binary Sizecoding) that implements a certain algorithm.
12

Hey guys, Hope you all are doing great. I am back with with a byte of python performance.

I have been playing on codingame.com a lot now a days during my weekends.

Its cool site for the player aka coders who want to try there hands into gaming domain.
Loading