Given a number n, find the ordered prime signatures and find the number of divisor of n.Any positive integer, ‘n’ can be expressed in the form of its prime factors. If ‘n’ has p_{1}, p_{2},  etc. as its prime factors, then n can be expressed as :
Arrange the obtained exponents of the prime factors of ‘n’ in non-decreasing order. The arrangement thus obtained is called the ordered prime signature of the positive integer ‘n’.
Example 1:
Input: n = 20
Output: 1 2
        6
Explaination: 20 can be written as 2^{2} * 5. The 
ordered pair is 2 1 and the factors are 1, 2, 4, 
5, 10, 20.
Example 2:
Input: n = 13
Output: 1
        2
Explaination: 13 itself is a prime number 
and it has two factors 1 and 13.
Your Task:
You do not need to read input or print anything. Your task is to complete the function orderedPrime() which takes n as input parameter and returns a list containing the powers in non-decreasing manner and the number of factors at the end of the list. The driver code will itself print the number of factors (last element of the returned list) in a new line.
Expected Time Complexity: O(nsqrt(n))
Expected Auxiliary Space: O(n)
Constraints:
2 ≤ n ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def orderedPrime(self, n):

        # code here

Solutions:
class Solution:

	def isprime(self, N):
		if N == 1:
			return False
		for i in range(2, int(N ** 0.5) + 1):
			if N % i == 0:
				return False
		return True

	def orderedPrime(self, n):
		a = []
		c = 0
		k = 0
		for i in range(1, n + 1):
			if n % i == 0:
				c += 1
				if self.isprime(i):
					d = n
					while d % i == 0:
						k = k + 1
						d = d // i
					a.append(k)
					k = 0
		a.sort()
		a.append(c)
		return a


class Solution:

	def orderedPrime(self, n):
		from collections import Counter
		rec = Counter()
		div = 2
		while n > 1:
			if n % div == 0:
				n //= div
				rec[div] += 1
			else:
				div += 1
		res = list(rec.values())
		res.sort()
		ans = 1
		for x in res:
			ans *= x + 1
		res.append(ans)
		return res


from functools import reduce

class Solution:

	def orderedPrime(self, n):
		arr = [True for i in range(n + 1)]
		p = 2
		while p * p < n:
			for i in range(p * p, n + 1, p):
				arr[i] = False
			p += 1
		d = []
		b = 1
		z = n
		for i in range(2, n + 1):
			a = 0
			while z % i == 0:
				a += 1
				z = z // i
			if a > 0:
				b = b * (a + 1)
				d.append(a)
		d.sort()
		return [*d, b]


class Solution:

	def orderedPrime(self, n):
		c = [True] * (n + 1)
		p = 2
		while p * p <= n:
			if c[p] == True:
				for i in range(p * p, n + 1, p):
					c[i] = False
			p = p + 1
		d = []
		z = n
		b = 1
		for i in range(2, n + 1):
			a = 0
			if c[i] == True:
				while z % i == 0:
					a = a + 1
					z = z // i
				if a > 0:
					b = b * (a + 1)
					d.append(a)
		d.sort()
		d.append(b)
		return d


from collections import Counter

class Solution:

	def orderedPrime(self, n):
		l1 = []
		l2 = []
		sieve = [1] * (n + 1)
		for i in range(n + 1):
			sieve[i] = i
		for i in range(2, int(n ** 0.5) + 1):
			if sieve[i] == i:
				for j in range(i * i, n + 1, i):
					if sieve[j] == j:
						sieve[j] = i
		n1 = n
		while n != 1:
			l1.append(sieve[n])
			n = n // sieve[n]
		dic = Counter(l1)
		for i in dic:
			l2.append(dic[i])
		l2.sort()
		count = 0
		if sieve[n1] == n1:
			count = 0
		else:
			for i in range(2, n1):
				if n1 % i == 0:
					count += 1
		l2.append(count + 2)
		return l2