跟着英雄大佬刷算法的第三天.......
数论基础
优化一:对于一个非素数n来说,如果x是n的一个因子。那么n/x也是n的一个因子,我们可以假设x
所以对于一个数n,判断它是否为一个素数我们需要确定的范围为【2,根号下n】。
优化二:
例1:
//不是素数返回0
bool isprime(int n)
{
if(n<2)
return false;
if(n>=2)
{
int num=sqrt(n);
int i=0;
for(i=2;i<=num;i++)
{
if(n%i==0)
return false;
}
}
return true;
}
题目1
int huiwen(int n)
{
int a=0;
if(n>0)
{
a=n%10;
n=n/10;
return a+10*huiwen(n);
}
return 0;
}
bool isprime(int n)
{
if(n<2)
{
return false;
}
if(n>=2)
{
int i=0;
for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
return false;
}
}
}
return true;
}
int primePalindrome(int n)
{
for(int i=n;i>=n;i++)
{
int ret=huiwen(i);
if(i==ret)
{
if(isprime)
{
return i;
}
}
}
return 0;
}
题目2:
int min(int x,int y)
{
int ret=x<y?x:y;
return ret;
}
int nthUglyNumber(int n)
{
int *ugly = (int *)malloc(sizeof(int) * n);
int a = 0;
int b = 0;
int c = 0;
ugly[0] = 1;//第一个丑数
for (int i = 1; i < n; i++)
{
int arr1 = ugly[a] * 2;
int arr2 = ugly[b] * 3;
int arr3 = ugly[c] * 5;
ugly[i] = min((min(arr1, arr2)), arr3);
if (ugly[i]== arr1)
{
a++;
}
if (ugly[i]== arr2)
{
b++;
}
if (ugly[i]==arr3)
{
c++;
}
}
return ugly[n - 1];
}