鱼C论坛

 找回密码
 立即注册
查看: 653|回复: 22

2019.1.11-C语言每周一练(共2题-第1题)

[复制链接]
最佳答案
2 
发表于 2019-1-11 15:43:17 | 显示全部楼层 |阅读模式
50鱼币
本帖最后由 小布丁 于 2019-1-11 16:20 编辑

题目: 请输出1000-10000之间所有的可逆素数,所谓可逆素数是指将一个素数的各位数字顺序颠倒过来构成的反序数仍然是素数。比如1009素数,各个位数反过来就是9001,仍然是素数。

要求:用循环的方式解决

效果图如下

小Q截图-20190111154242.png

关于评判标准,可以参考此帖:https://fishc.com.cn/thread-129371-1-1.html

第二题传送门:https://fishc.com.cn/thread-129370-1-1.html

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
1348 
发表于 2019-1-11 16:44:55 | 显示全部楼层
思路:
1 找到范围内的所有素数并放到一个数组中
2 判断该数组中的逆是否也在改数组中
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-11 19:35:18 | 显示全部楼层
本帖最后由 我是个汉子 于 2019-1-12 20:58 编辑

#include<stdio.h>
int fun(int a)
{
    int i;
    for(i=2; i<a; i++)
        if(a%i==0)
            return 0;
    return 1;
}

void put()
{
    int i,sum,t;
    for(i=1000; i<10000; i++)
    {
        t=i;
        sum=0;
        while(t)
        {
            sum=sum*10+t%10;
            t/=10;
        }
        if(fun(i) && fun(sum))
            printf("%5d",i);
    }
}

int main()
{
    put();
}



                               
登录/注册后可看大图

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
452 
发表于 2019-1-11 22:06:54 | 显示全部楼层
你的输出不对吧?

  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdbool.h>

  4. bool IsPrimeNumber(size_t number)
  5. {
  6.         if(number <= 3)
  7.                 return number > 1;

  8.         size_t k = (size_t)sqrt(number);
  9.         for(size_t i = 2; i <= k; ++i)
  10.         {
  11.                 if(number % i == 0)
  12.                         return false;
  13.         }
  14.         return true;
  15. }

  16. size_t ReverseNumber(size_t number)
  17. {
  18.         size_t result = 0;
  19.         while(number)
  20.         {
  21.                 result = result * 10 + (number % 10);
  22.                 number /= 10;
  23.         }
  24.         return result;
  25. }

  26. int main(void)
  27. {
  28.         for(size_t i = 1000; i < 10000; ++i)
  29.         {
  30.                 if(IsPrimeNumber(i))
  31.                 {
  32.                         if(IsPrimeNumber(ReverseNumber(i)))
  33.                                 printf("%u ", i);
  34.                 }
  35.         }
  36.         printf("\n");
  37.         return 0;
  38. }
复制代码


1.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
 楼主| 发表于 2019-1-11 22:54:57 | 显示全部楼层
人造人 发表于 2019-1-11 22:06
你的输出不对吧?

没差别,只不过你的把正反都一样的也输出来了,7699和9967都输出了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
452 
发表于 2019-1-12 08:49:32 | 显示全部楼层
本帖最后由 人造人 于 2019-1-12 08:51 编辑
小布丁 发表于 2019-1-11 22:54
没差别,只不过你的把正反都一样的也输出来了,7699和9967都输出了


嗯,我明白了
我没有好的方法去除重复,可以问一下你是怎么做的吗?话说你什么时候公布参考答案?下个星期?^_^
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdbool.h>

  4. bool IsPrimeNumber(size_t number)
  5. {
  6.         if(number <= 3)
  7.                 return number > 1;

  8.         size_t k = (size_t)sqrt(number);
  9.         for(size_t i = 2; i <= k; ++i)
  10.         {
  11.                 if(number % i == 0)
  12.                         return false;
  13.         }
  14.         return true;
  15. }

  16. size_t ReverseNumber(size_t number)
  17. {
  18.         size_t result = 0;
  19.         while(number)
  20.         {
  21.                 result = result * 10 + (number % 10);
  22.                 number /= 10;
  23.         }
  24.         return result;
  25. }

  26. bool ExistNumber(size_t buf[], size_t size, size_t number)
  27. {
  28.         for(size_t i = 0; i < size; ++i)
  29.         {
  30.                 if(buf[i] == number)
  31.                         return true;
  32.         }
  33.         return false;
  34. }

  35. int main(void)
  36. {
  37.         size_t buf[512];
  38.         size_t index = 0;
  39.         for(size_t i = 1000; i < 10000; ++i)
  40.         {
  41.                 if(IsPrimeNumber(i))
  42.                 {
  43.                         size_t r = ReverseNumber(i);
  44.                         if(IsPrimeNumber(r))
  45.                         {
  46.                                 if(!ExistNumber(buf, index, r))
  47.                                         buf[index++] = i;
  48.                         }
  49.                 }
  50.         }

  51.         for(size_t i = 0; i < index; ++i)
  52.         {
  53.                 printf("%u ", buf[i]);
  54.         }
  55.         printf("\n");
  56.         return 0;
  57. }
复制代码


1.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-12 10:38:58 | 显示全部楼层
#include <stdio.h>
void output();
int judge(int i);
int main()
{
output();
getchar();
return 0;
}
void output()
{int i=1000,n,re_i,a,b,c,d;
for(;i<10000;i++)
        {a=i/1000;
        b=i/100%10;
        c=i/10%10;
        d=i%10;
        re_i=d*1000+c*100+b*10+a;
        if(judge(i)&&judge(re_i))
                printf("%6d",i);
        }

}
int judge(int i)
{int n=2;
for(;n<i/2;n++)
        if(i%n==0)
                return 0;
return 1;
}
微信图片_20190112103738.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
 楼主| 发表于 2019-1-12 12:29:06 | 显示全部楼层
人造人 发表于 2019-1-12 08:49
嗯,我明白了
我没有好的方法去除重复,可以问一下你是怎么做的吗?话说你什么时候公布参考答案?下个 ...

下周一见
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-12 18:38:59 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <stdbool.h>

  3. bool IsP(int n){
  4.         int i;
  5.         for(i=2; i<n; i++) {
  6.                 if(n%i == 0)
  7.                         break;
  8.         }
  9.         if(n == i)
  10.                 return true;
  11.         else
  12.                 return false;
  13. }


  14. int main(){
  15.         int a[5000];
  16.         int b[5000];
  17.         int k = 0;
  18.         for(int j=1000; j<=10000; j++) {
  19.                 if( IsP(j) ) {
  20.                         a[k] = j;
  21.                         k += 1;
  22.                 }
  23.         }

  24.         for(int m=0; m<=k; m++) {
  25.                 b[m] = (a[m]%10 * 1000 + a[m]%100/10 * 100 + a[m]/100%10 *10 + a[m]/1000);
  26.                 if( IsP(b[m]) ) {
  27.                         printf("%d ", a[m]);
  28.                 }
  29.         }

  30.         printf("\n");
  31.         return 0;
  32. }
复制代码
1.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
35 
发表于 2019-1-12 21:06:50 | 显示全部楼层
本帖最后由 行客 于 2019-1-12 22:16 编辑

  1. // PrimeNumber.cpp : Defines the entry point for the console application.
  2. // Code by xingke.       

  3. #include "stdafx.h"
  4. #include "stdio.h"
  5. #include <math.h>

  6. int IsPrimeNumber(int number)
  7. {
  8.         int k = (int)sqrt((double)number);        //一个数能被 2 ~ number的开方 整除就是合数,反之是素数
  9.         int i = 0;

  10.         for(i = 2;i <= k;i ++)
  11.         {
  12.                 if(number%i == 0)
  13.                         break;
  14.         }

  15.         return i > k ? number : 0;
  16. }

  17. int ReverseNumber(int number)
  18. {
  19.         int result = 0;

  20.         while(number)
  21.         {
  22.                 result = result * 10 + (number % 10);        //取得number的最低位
  23.                 number /= 10;        //number右移1位
  24.         }

  25.         return result;
  26. }

  27. int main(int argc, char* argv[])
  28. {
  29.         bool map[10000]={0};        //原想采用bit搞成奇偶校验,但不好理解。这里暂且采用这种模式

  30.         for(int i = 1000; i <= 10000; i++)
  31.         {
  32.                 int IsP=IsPrimeNumber(i);        //IsP这个变量可以节省,这里这样定义为了方便他人理解
  33.                 int IsPR=IsPrimeNumber(ReverseNumber(i));
  34.                 if(IsP & IsPR)
  35.                 {
  36.                         if(!(map[IsP] | map[IsPR]))        //这里的map[IsP] 也可以用map[i]
  37.                         {
  38.                                 map[IsP] = 1;
  39.                                 printf("%u ", i);
  40.                         }
  41.                 }
  42.         }

  43.         return 0;
  44. }
复制代码


我上传图片怎么一直显示错误?借用小布丁的图片:

                               
登录/注册后可看大图
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-12 23:38:10 | 显示全部楼层
#include <stdio.h>
#include <Windows.h>

//--这是的判断是不是素数,已经排偶数排除在外了
//--所以,判断的标准从3开始到这个数的1/3处
//--函数返回0表示不是素数,否则表示是素数
unsigned int IsPrime_NoEven(unsigned int nData)
{
        unsigned int i;
        unsigned int j = nData / 3 + 1;
       
        for (i = 3; i < j; i++)
        {
                if (0 == (nData % i)) return 0;
        }
        return 1;
}

void main(void)
{
        unsigned int i,j,k = 0;

        unsigned int nThdBit; //--千位数
        unsigned int nHndBit; //--百位数
        unsigned int nTenBit; //--十位数
        unsigned int nBitBit; //--个位数

        //--1000,9999,10000肯定不是素数,所以排除在外,非2偶数也不是素数,所以i每次增加2
        for (i = 1001; i < 9998; i += 2)
        {
                nThdBit = i / 1000; //--提取千位数
                nBitBit = i % 10;   //--提取个位数

                if (5 == nThdBit) continue; //--千位数是5,肯定不是可逆素数
                if (5 == nBitBit) continue; //--个位数是5,肯定不是素数
                if (!(nThdBit & 0x00000001)) continue; //--如果千位是偶数,肯定不是可逆素数
                if (!IsPrime_NoEven(i))      continue; //--如果这个数不是素数,继续

                nHndBit = (i / 100) % 10; //--提取百位数
                nTenBit = (i / 10) % 10;  //--提取十位数

                //--组成逆序数
                j = nBitBit * 1000 + nTenBit * 100 + nHndBit * 10 + nThdBit;
                if (!IsPrime_NoEven(j)) continue; //--如果组成的逆序数不是素数,继续

                //--如果是逆序数,打印原数
                printf("%d  ",i);
       
                if ( ++ k >= 12)
                {
                        k = 0;
                        printf("\n");
                }
        }

        printf("\n\n");
        system("pause");

}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-12 23:39:56 | 显示全部楼层
r:\1.jgp
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-12 23:40:33 | 显示全部楼层
谁能教我,怎么发图片?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-12 23:41:31 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <Windows.h>

  3. //--这是的判断是不是素数,已经排偶数排除在外了
  4. //--所以,判断的标准从3开始到这个数的1/3处
  5. //--函数返回0表示不是素数,否则表示是素数
  6. unsigned int IsPrime_NoEven(unsigned int nData)
  7. {
  8.         unsigned int i;
  9.         unsigned int j = nData / 3 + 1;
  10.        
  11.         for (i = 3; i < j; i++)
  12.         {
  13.                 if (0 == (nData % i)) return 0;
  14.         }
  15.         return 1;
  16. }

  17. void main(void)
  18. {
  19.         unsigned int i,j,k = 0;

  20.         unsigned int nThdBit; //--千位数
  21.         unsigned int nHndBit; //--百位数
  22.         unsigned int nTenBit; //--十位数
  23.         unsigned int nBitBit; //--个位数

  24.         //--1000,9999,10000肯定不是素数,所以排除在外,非2偶数也不是素数,所以i每次增加2
  25.         for (i = 1001; i < 9998; i += 2)
  26.         {
  27.                 nThdBit = i / 1000; //--提取千位数
  28.                 nBitBit = i % 10;   //--提取个位数

  29.                 if (5 == nThdBit) continue; //--千位数是5,肯定不是可逆素数
  30.                 if (5 == nBitBit) continue; //--个位数是5,肯定不是素数
  31.                 if (!(nThdBit & 0x00000001)) continue; //--如果千位是偶数,肯定不是可逆素数
  32.                 if (!IsPrime_NoEven(i))      continue; //--如果这个数不是素数,继续

  33.                 nHndBit = (i / 100) % 10; //--提取百位数
  34.                 nTenBit = (i / 10) % 10;  //--提取十位数

  35.                 //--组成逆序数
  36.                 j = nBitBit * 1000 + nTenBit * 100 + nHndBit * 10 + nThdBit;
  37.                 if (!IsPrime_NoEven(j)) continue; //--如果组成的逆序数不是素数,继续

  38.                 //--如果是逆序数,打印原数
  39.                 printf("%d  ",i);
  40.        
  41.                 if ( ++ k >= 12)
  42.                 {
  43.                         k = 0;
  44.                         printf("\n");
  45.                 }
  46.         }

  47.         printf("\n\n");
  48.         system("pause");

  49. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
12 
发表于 2019-1-13 00:46:47 | 显示全部楼层
本帖最后由 Croper 于 2019-1-14 01:12 编辑

不知是否允许使用c++,算法应该是通用的
使用了stl提供的容器和链表,不行的话请我再上个不用stl库的
感觉时间和空间复杂度都尽量压缩了
  1. //使用了stl中的容器和链表,
  2. //看点为使用了较好的判断和得到素数的函数,以及较好的去重方法

  3. #include <iostream>
  4. #include <vector>
  5. #include <list>

  6. using namespace std;

  7. int prime(int);
  8. bool IsPrime(int);
  9. int ReverseInt(int);
  10. void solution(int,int);

  11. int prime(int i)  //返回第n个素数,嗯第0个是2
  12. {
  13.         static vector<int> primelist = { 2 }; //内部储存所有素数的容器,使用static,使得只有在第一次申请时会进行计算,后续直接从vector里读取响应的数
  14.         if (i < primelist.size()) return primelist[i];
  15.         int n = primelist.back();                                       //如果容器长度不足,则扩建容器使其长度到达i+1;
  16.         while (i >= primelist.size()) if (IsPrime(++n)) primelist.push_back(n);
  17.         return primelist[i];
  18. }


  19. bool IsPrime(int n) //判断是否是素数
  20. {
  21.         for (int i = 0; prime(i) <= sqrt(n); ++i) if (n%prime(i) == 0) return false;  //判断素数只要一个数不能被小于等于其平方根的所有素数除尽则一定是一个素数
  22.         return true;
  23. }


  24. int ReverseInt(int n)
  25. {
  26.         int ans = 0;
  27.         while (n > 0)
  28.         {
  29.                 ans *= 10;
  30.                 ans += n % 10;
  31.                 n /= 10;
  32.         }
  33.         return ans;
  34. }


  35. void solution(int minnum,int maxnum)    //主体部分,可以改变输入的最大最小值
  36. {
  37.         list<int> checklist; //去重用,建立一个存储已检查元素的链表
  38.         list<int>::iterator iter;
  39.         int i, n, m;
  40.         bool b;
  41.         for (i = 0; prime(i) <= maxnum; ++i)  //这里只会循环素数,去掉了大量的无用循环
  42.         {
  43.                 n = prime(i);     //n即为第i个素数
  44.                 if (n < minnum) continue;

  45.                 b = false;
  46.                 for (iter = checklist.begin(); iter != checklist.end(); ++iter) if (n == *iter)  //n是否被检查过               
  47.                 {
  48.                         checklist.erase(iter);  //在链表中移除,尽量缩短链表,提高效率;
  49.                         b = true;
  50.                         break;
  51.                 }
  52.                 if (b) continue;  //如果已被检查过,那么跳过


  53.                 m = ReverseInt(n);
  54.                 if (IsPrime(m))
  55.                 {
  56.                         if (m != n) checklist.push_back(m);  //将m加入检查用链表,回文素数就不用了(1000-9999中有回文素数么?)
  57.                         cout << n << " ";
  58.                 }
  59.         }
  60. }

  61. int main()
  62. {
  63.         solution(1000, 9999);
  64.         system("pause");
  65. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
35 
发表于 2019-1-13 12:07:23 | 显示全部楼层
Croper 发表于 2019-1-13 00:46
不知是否允许使用c++,算法应该是通用的
使用了stl提供的容器和链表,不行的话请我再上个不用stl库的
感 ...

这个思路也很好,你的代码非常优秀!本来我一开始想用list来实现,后来觉得有点C++了,就改成了上面的样子。我那个代码有点空间换时间的意思。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-13 12:56:20 | 显示全部楼层
请问一下为什么要去除重复?楼主说7699和9967只用输出一个...但是题目要求不是1000-10000之间的所有可逆素数么?7699和9967显然不是一个数啊?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-13 22:15:30 | 显示全部楼层
  1. /*
  2. 题目: 请输出1000-10000之间所有的可逆素数,
  3. 所谓可逆素数是指将一个素数的各位数字顺序颠倒过来构成的反序数仍然是素数。
  4. 比如1009素数,各个位数反过来就是9001,仍然是素数。
  5. 要求:用循环的方式解决
  6. */
  7. #include <stdio.h>
  8. #include <math.h>
  9. int main()
  10. {
  11.         int limit,temp, num = 1001,num_inverse; //素数一定是奇数,从1001开始
  12.         for (;num < 10000; num=num+2)
  13.         {
  14.                 if (!((num / 1000) % 2)) //去掉第一个数字是偶数的数。这样的数一定不是可逆素数
  15.                         continue;
  16.                 limit = (int)sqrt(num);//判断是否为素数,一直除到这个数开根号那么大,如果仍然不能整除则为素数
  17.                 for (temp=3;temp <=limit ;temp=temp+2)//temp作为除数,一次加2,因为被除数都是奇数,不可能被偶数整除
  18.                 {
  19.                         if (!(num%temp))
  20.                                 break;
  21.                         else
  22.                                 continue;
  23.                 }
  24.                 if (temp > limit) //如果大于号成立,则该数是素数
  25.                 {
  26.                         num_inverse = (num % 10) * 1000 + (num / 10) % 10 * 100 + (num / 100) % 10 * 10 + (num / 1000);
  27.                         limit = (int)sqrt(num_inverse);
  28.                         for (temp = 3; temp <= limit; temp = temp + 2)//在此判断是否为素数
  29.                         {
  30.                                 if (!(num_inverse%temp))
  31.                                         break;
  32.                                 else
  33.                                         continue;
  34.                         }
  35.                         if (temp > limit)
  36.                         {
  37.                                 if (num_inverse < num) //去掉重复数字
  38.                                         continue;
  39.                                 printf("%d ", num);//打印数字
  40.                         }
  41.                                
  42.                         else
  43.                                 continue;
  44.                 }
  45.                 else
  46.                         continue;
  47.         }
  48.         getchar();
  49.         return 0;
  50. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-13 22:25:04 | 显示全部楼层
本帖最后由 xkcx1988 于 2019-1-13 22:27 编辑

怎么上传结果图片呀
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-1-14 00:39:18 | 显示全部楼层
  1. #include <stdio.h>

  2. bool IsPrime(int num)                //判断素数
  3. {
  4.         int i;

  5.         for (i = 2; i <= num; i++)
  6.         {
  7.                 if (0 == num % i)
  8.                 {
  9.                         break;
  10.                 }
  11.         }

  12.         if (i == num)
  13.         {
  14.                 return true;
  15.         }
  16.         else
  17.         {
  18.                 return false;
  19.         }
  20. }

  21. int AntiNum(int num)                //求逆
  22. {
  23.         int anti_num, a, b, c, d;

  24.         a = (num % 10) * 1000;                                //逆数的千位
  25.         b = (num % 100 - num % 10) * 10;        //逆数的百位
  26.         c = int((num % 1000 - num % 100) * 0.1);        //逆数的十位
  27.         d = int((num - num % 1000) * 0.001);        //逆数的个位
  28.         anti_num = a + b + c + d;

  29.         return anti_num;
  30. }

  31. int main(void)
  32. {
  33.         int num, val;

  34.         for (num = 1000; num < 10001; num++)
  35.         {
  36.                 val = AntiNum(num);
  37.                
  38.                 if (IsPrime(num) && IsPrime(val))        //判断本体和逆数
  39.                 {
  40.                         if (num < val)
  41.                         {
  42.                                 printf("%d ", num);
  43.                         }       
  44.                 }
  45.         }
  46.         putchar('\n');

  47.         return 0;
  48. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2019-1-22 01:43

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表