Problem 47 Distinct primes factors （分解因子）

傷城~ 2022-07-15 03:22 169阅读 0赞

## Distinct primes factors ##

### Problem 47 ###

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7  
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23  
645 = 3 × 5 × 43  
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

<table> 
 <tbody> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td> 
        <div style="text-align:right"> 
         <span style="font-size:18px">Answer:</span> 
        </div> </td> 
       <td><strong><span style="font-size:18px">134043</span></strong></td> 
      </tr> 
      <tr> 
       <td colspan="2"><span style="color:rgb(153,153,153)"><span style="font-size:18px">Completed on Mon, 31 Oct 2016, 09:55</span></span></td> 
      </tr> 
     </tbody> 
    </table> </td> 
  </tr> 
 </tbody> 
</table>

代码：

#include<bits/stdc++.h>
    using namespace std;
    void factor(set<int>& s,  int n)
    {
        if(n==1)return;
        int k = (int)sqrt(n);
        int num = 2;
        while( n%num != 0)
    	{
            if(num >= k) //最后结束条件 
    		{
    		  s.insert(n); 
    		  return;
    		}
            if(num > 2) num+=2;
            else num++;
        }
        s.insert(num);
        factor(s, n/num);
    }
    
    int main()
    {
        set<int> s;
        int counter = 0;
    	int ans = 0;
        for(int i=1; ;i++)
    	{
            factor(s, i);
            if(s.size()== 4)
    		{ 
                if(ans == 0) ans = i;
                counter++;
            }
    		else
    		{ 
                ans = 0;
                counter = 0;
            }
    
            if(counter==4)
    		{   
    			cout<<ans<<endl;
                s.clear();
                break;
            }
            s.clear();
        }
        return 0;
    
    }