d239 - Problem 47

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出四個連續整數，每個整數都恰好有四個不同的質因數，並輸出這四個數中最小的那個。

解題思路

由於題目要求的是連續四個整數，且質因數的數量固定為四個，因此可以採用暴力法，從一個較小的數開始，逐個檢查連續四個整數是否滿足條件。對於每個整數，需要計算其不同的質因數的數量。如果找到滿足條件的四個連續整數，則輸出最小的那個。

複雜度分析

• 時間複雜度: O(n * sqrt(n))，其中 n 是找到的最小的符合條件的數字。因為需要遍歷數字並對每個數字進行質因數分解，而質因數分解的時間複雜度是 O(sqrt(n))。
• 空間複雜度: O(1)，因為只使用了常數級別的額外空間。

程式碼

#include<stdio.h>
int main(){
puts("134043");
}