Python program to find number of integers which has exactly x divisors
Number of integers which has exactly x divisors in python
Here, in this page we will discuss the program that count the number of integers which has exactly x divisors in python . Numbers dividing with self or 1 are called prime numbers but numbers having multiple divisors are called composite numbers.
Here, in this page we will discuss the two different ways for finding the required count of numbers that have exactly x divisors. These two methods are given below,
- Method 1 : Naive approach
- Method 2 : Efficient approach
Method 1 :
- Declare a variable count =0, to count the required numbers with x factors.
- Run a loop for range 1 to n.
- Inside that take a variable count_factors = 0, that will count the factors of ith.
- Now, run a inner loop.
- And increase the count_factors if it’s is factor of ith number.
- Check if count_factors == X, then increment the count by 1.
- At last print the count value.
Method 1 : Code in Python
Run
Number = 7
Divisor = 2
#count is to count total number of Numbers with exact divisor
count = 0
#driver loop
for i in range(1,Number+1):
#count_factors checks the total number of divisors
count_factors = 0
#loop to find number of divisors
for j in range(1,i+1):
if i % j == 0:
count_factors += 1
else:
pass
if count_factors == Divisor:
count +=1
#for break in line between Numbers and total count
print(count)
Output :
4
Method 2 :
In this method we will use the efficient way for counting the factors that used in method 1. We use the sieve of eratosthenes for counting the factors.
Method 2 : Code in Python
Run
import math;
def sieve(primes, x):
primes[1] = False;
i = 2;
while (i * i <= x):
if (primes[i] == True):
j = 2;
while (j * i <= x):
primes[i * j] = False;
j += 1;
i += 1;
def nDivisors(primes, x, a, b, n):
result = 0;
v = [];
for i in range(2, x + 1):
if (primes[i]):
v.append(i);
for i in range(a, b + 1):
temp = i;
total = 1;
j = 0;
k = v[j];
while (k * k <= temp):
count = 0;
while (temp % k == 0):
count += 1;
temp = int(temp / k);
total = total * (count + 1);
j += 1;
k = v[j];
if (temp != 1):
total = total * 2;
if (total == n):
result += 1;
return result;
def countNDivisors(a, b, n):
x = int(math.sqrt(b) + 1);
primes = [True] * (x + 1);
sieve(primes, x);
return nDivisors(primes, x, a, b, n);
n = 7;
x = 2;
print(countNDivisors(1, n, x));
Output :
4
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Login/Signup to comment
C++ solution
#include
using namespace std;
bool isPrime(int n);
void Numberwith(int n)
{
for (int i = 2; i * i <= n; i++)
{
if (isPrime(i))
{
if (i * i <= n)
{
cout << i * i << " ";
}
}
}
}
bool isPrime(int n)
{
if(n==0 || n==1 )
{
return false;
}
for (int i = 2; i * i > n;
Numberwith(n);
return 0;
}
public class JavaApplication1
{
public static void main(String[] args)
{
Scanner obj = new Scanner(System.in);
int n,x;
n = obj.nextInt();
x = obj.nextInt();
for(int i=1;i<=n;i++)
{
int c=0;
String s="";
for(int j=1;j”+s);
System.out.println();
}
}
}
}
public class JavaApplication1
{
public static void main(String[] args)
{
Scanner obj = new Scanner(System.in);
int n,x;
n = obj.nextInt();
x = obj.nextInt();
for(int i=1;i<=n;i++)
{
int c=0;
String s="";
for(int j=1;j”+s);
System.out.println();
}
}
}
}
public class JavaApplication1
{
public static void main(String[] args)
{
Scanner obj = new Scanner(System.in);
int n,x;
n = obj.nextInt();
x = obj.nextInt();
for(int i=1;i<=n;i++)
{
int c=0;
String s="";
for(int j=1;j”+s);
System.out.println();
}
}
}
}
Code in Java :
import java.util.Scanner;
public class Exactly_n_divisors
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.print(“Enter range: “);
int range = sc.nextInt();
System.out.print(“Enter exact number of divisors: “);
int exact = sc.nextInt();
int total = 0;
System.out.println(“Numbers which has exactly “+exact+ ” divisors are “);
for(int number=1; number<=range; number++)
{
int count = 0;
for(int divisor=1; divisor<=number; divisor++)
{
if(number%divisor == 0)
count++;
}
if(count == exact)
{
System.out.println(number+" ");
total++;
}
}
System.out.println("Total numbers: "+total);
}
}
/* c++ program to find number of integers in given range, which has exactly x divisors */
#include
using namespace std;
int main()
{
int count=0,count1=0,n,x;
/*input range*/
cout<>n;
/*input number of divisors*/
cout<>x;
for (int i=1;i<=n;i++)
{
count1=0;
for (int j=1;j<=i;j++)
{
if (i%j==0)
{
count1++;
}
}
if (count1==x)
{
count++;
/*printing the integers wich has exactly x divisors */
cout<<i<<" ";
}
}
/* printing the total number of integers in the range which has exactly x divisors */
cout<<"\n"<<count;
return 0;
}
/* c++ program to find number of integers in a given range, which has exactly x divisors */
#include
using namespace std;
int main()
{
int count=0 ,count1=0, n, x;
// input range
cout<>n;
// input number of divisors
cout<>x;
for (int i=1; i<=n; i++)
{
count1=0;
for (int j=1; j<=i; j++)
{
if (i%j==0)
{
count1++;
}
}
if (count1==x)
{
count++;
// printing the integers ( in given range ) which has exactly x divisors
cout<<i<<" ";
}
}
// printing the total number of integers in the range which has exactly x divisors
cout<<"\n"<<count;
return 0;
}
program in c:—->
void main()
{
int n,x,count=0,i=0,a[10],j;
printf(“enter the range”);
scanf(“%d”,&n);
printf(“enter the exact divisor”);
scanf(“%d”,&x);
for(i=1;i<=n;i++)
{
count=0;
for(j=1;j=0)
{
printf(“%d\t”,a[i]);
i–;
}
}
program in c:—–
#include
void main()
{
int n,x,count=0,i=0,a[10],j;
printf(“enter the range”);
scanf(“%d”,&n);
printf(“enter the exact divisor”);
scanf(“%d”,&x);
for(i=1;i<=n;i++)
{
count=0;
for(j=1;j=0)
{
printf(“%d\t”,a[i]);
i–;
}
}
// in c
#include
int main()
{
int n,i,c=0,d;
printf(“enter last range number:”);
scanf(“%d”,&n);
printf(“enter exactly n divisor:”);
scanf(“%d”,&d);
for( i=1;i<=n;i++)
{ int count=0;
for(int j=1;j<=i;j++)
{
if(i%j==0)
{ //printf("%d\t",i);
count++;
}
}
if(count==d)
{
c++;
printf("%d\t",i);
}
}
printf("\n%d",c);
return 0;
}
#program in java
import java.util.*;
public class EqualDivisorInRange {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println(“Enter range: “);
int r=sc.nextInt();
System.out.println(“Enter maxm divisor of number: “);
int d=sc.nextInt();
int c[]=new int[r];
int k=0;
for(int i=1;i<=r;i++)
{
int count=0;
for(int j=1;j<=i;j++)
{
if(i%j==0)
{
count++;
}
}
if(count==d)
{
c[k]=i;
k++;
}
}
System.out.println("Number are with equal divisor: ");
for(int p=0;p<k;p++)
{
System.out.println(c[p]);
}
}
}