计算小于 N 的完美正方形的乘积

原文:https://www . geesforgeks . org/count-number-小于 n-哪些是完美平方的乘积/

给定一个整数 N，任务是计算小于 N 的数 P，使得 P 是两个不同的完美平方的乘积。 例 :

Input : N = 36
Output : 5
Numbers are 4 = 12 * 22, 
9 = 12 * 32, 
16 = 12 * 42, 
25 = 12 * 52, 
36 = 12 * 62

Input : N = 1000000
Output : 999

方法:让我们考虑一个数字 P = (a 2 * b 2 )这样 P < = N 所以我们有(a 2 * b 2 ) < = N 这可以写成(a * b) < = sqrt(N)。 所以我们要对(a，b)进行计数，这样(a * b) < = sqrt(N)和 a < = b. 让我们取一个数 Q = (a * b) 这样 Q < = sqrt(N)。 取 a = 1，我们有 b = sqrt(N)–1 个数字，这样，(a * b = Q < = sqrt(N))。 因此我们可以拥有所有 sqrt(N)–1 的数字，这样(a2* b2)<= N . 以下是上述方法的实现:

C++

// C++ program to count number less
// than N which are product of
// any two perfect squares

#include <bits/stdc++.h>
using namespace std;

// Function to count number less
// than N which are product of
// any two perfect squares
int countNumbers(int N)
{
    return int(sqrt(N)) - 1;
}

// Driver program
int main()
{
    int N = 36;

    cout << countNumbers(N);

    return 0;
}

Java 语言(一种计算机语言，尤用于创建网站)

// Java program to count number less
// than N which are product of
// any two perfect squares
import java.util.*;

class solution
{

// Function to count number less
// than N which are product of
// any two perfect squares
static int countNumbers(int N)
{
    return (int)Math.sqrt(N) - 1;
}

// Driver program
public static void main(String args[])
{
    int N = 36;

    System.out.println(countNumbers(N));

}

}

//This code is contributed by
// Surendra_Gangwar

Python 3

# Python 3 program to count number
# less than N which are product of
# any two perfect squares
import math

# Function to count number less
# than N which are product of
# any two perfect squares
def countNumbers(N):
    return int(math.sqrt(N)) - 1

# Driver Code
if __name__ == "__main__":
    N = 36

    print(countNumbers(N))

# This code is contributed
# by ChitraNayal

C

// C# program to count number less
// than N which are product of
// any two perfect squares
using System;

class GFG
{
// Function to count number less
// than N which are product of
// any two perfect squares
static int countNumbers(int N)
{
    return (int)(Math.Sqrt(N)) - 1;
}

// Driver Code
public static void Main()
{
    int N = 36;

    Console.Write(countNumbers(N));
}
}

// This code is contributed
// by Akanksha Rai

服务器端编程语言（Professional Hypertext Preprocessor 的缩写）

<?php
// PHP program to count number less
// than N which are product of
// any two perfect squares

// Function to count number less
// than N which are product of
// any two perfect squares
function countNumbers($N)
{
    return (int)(sqrt($N)) - 1;
}

// Driver Code
$N = 36;
echo countNumbers($N);

// This code is contributed by akt_mit
?>

java 描述语言

<script>
    // Javascript program to count number less
    // than N which are product of
    // any two perfect squares

    // Function to count number less
    // than N which are product of
    // any two perfect squares
    function countNumbers(N)
    {
        return parseInt(Math.sqrt(N), 10) - 1;
    }

    let N = 36;

    document.write(countNumbers(N));

</script>

Output: 

5

时间复杂度: O(log(N))

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/33086.html