k145 - 街燈管理員

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在 1 到 n 的整數中，有多少個數的因數個數為奇數。

解題思路

一個數的因數個數為奇數，當且僅當這個數是完全平方數。因此，問題轉化為計算 1 到 n 之間有多少個完全平方數。 程式碼直接利用平方根的特性，迴圈直到 i*i > n，每次迴圈增加計數器 ct 和 i。迴圈結束時，ct 的值即為 1 到 n 之間完全平方數的個數。

複雜度分析

• 時間複雜度: O(sqrt(n))
• 空間複雜度: O(1)

程式碼

#include <bits/stdc++.h>
using namespace std;
long long n,ct,i=1;
int main(){
	cin >> n;
	while(i*i<=n)++ct,++i;
	cout << ct ;
}