Problem 41 Pandigital prime (暴力set+vector)

分手后的思念是犯贱 2022-07-15 02:41 208阅读 0赞

Pandigital prime

Problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?




















Answer:
7652413
Completed on Sun, 30 Oct 2016, 06:32

代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int is_pandigital(long long n)
  4. {
  5. if(n<=0) return 0;
  6. vector<int> v;
  7. while(n != 0)
  8. {
  9. v.push_back(n%10);
  10. n/=10;
  11. }
  12. set<int> set_n(v.begin(),v.end()); //转化为set,去重
  13. int len = v.size();
  14. if(set_n.size() == len) //不含重复值
  15. {
  16. sort(v.begin(),v.end()); //默认从小到大排序
  17. for (int i=0;i<len;i++) //digits=1,2,3...
  18. {
  19. if (v[i] != (i+1))
  20. {
  21. return 0;
  22. }
  23. }
  24. return 1;
  25. }
  26. return 0;
  27. }
  28. int is_prime(long long n)
  29. {
  30. if (n == 2)
  31. return 1;
  32. if (n % 2 == 0)
  33. return 0;
  34. long long i;
  35. for (i = 3; i * i <= n; i += 2)
  36. if (n % i == 0)
  37. return 0;
  38. return 1;
  39. }
  40. int main()
  41. {
  42. long long n;
  43. for (n = 7654321; n >= 1234567; n -= 2)
  44. if (is_pandigital(n) && is_prime(n)) break;
  45. printf("%lld\n", n);
  46. return 0;
  47. }

发表评论

表情:
评论列表 (有 0 条评论,208人围观)

还没有评论,来说两句吧...

相关阅读