313. 超级丑数-暴力解法

313. 超级丑数

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

示例 1：

输入：n = 12, primes = [2,7,13,19]
输出：32
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

示例 2：

输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。

解题代码如下：

bool find(int val,int* primes, int primesSize){
    
    if(val==1){
    
        return true;
    }

    for(int i=0;i<primesSize;i++){
    
        if(primes[i]==val){
    
            return true;
        }
    }
    return false;
}

bool re(int n){
    
    if(n==1){
    
        return true;
    }
    for(int i=2;i<=n/2;i++){
    
        if(n%i==0){
    
            return false;
        }
    }
    return true;
}

int nthSuperUglyNumber(int n, int* primes, int primesSize){
    
    int count=0;
    // for(int i=1;i<10;i++){
    
    // if(re(i)){
    
    // printf("%d ",i);
    // }
    // }
    for(int i=1;i<100000;i++){
    
     // printf("--%d ",i);
        int r=0;
        if(i==1){
    
            count++;
             if(count==n){
    
            return i;
         }
        }
        else{
    
            for(int j=1;j<=i/2;j++){
    
                if(i%j==0){
    
                   
                    if(re(j)){
    
               // printf("|%d ",j);
                        if(find(j,primes,primesSize)){
    
                       
                        }
                        else{
    
                            r=1;
                            break;
                        }
                    }
                    if(re(i/j)){
    
                   // printf("|%d ",i/j);
                          if(find(i/j,primes,primesSize)){
    
                     
                        }
                         else{
    
                            r=1;
                            break;
                        }
                    }
                }

            }
            if(r==0){
    
                count++;
                if(count==n){
    return i;}
             // printf("count %d %d",i,count);
            }
        }
       
         

    }
return 0;
}