“This is the 10th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

I. Problem description

Visitors to Planet X are given an integer as a visitor number.

The king of planet X has a quirk. He only likes the numbers 3,5 and 7.

The king gave visitors a prize if their numbers contained only factors: 3, 5, and 7.

Let’s look at the top 10 lucky numbers:

35 7 9 15 21 25 27 35 45

So the 11th lucky number is 49

Xiao Ming received a lucky number 59084709587505, when he went to receive the award, they asked him to tell exactly how many lucky numbers this is, or he won’t get the prize.

Please help Xiao Ming to calculate the number 59084709587505.

Two, the title requirements

inspection

2. The recommended time is 5~15minCopy the code

Operating limits

  • Maximum running time: 1s
  • Maximum running memory: 128M

Third, problem analysis

First, the number can only contain 3, 5, and 7 factors. At first I wanted to use the for loop and judge the numbers from 1 to 59084709587505 one by one.

It turns out no, one problem is too big to solve completely, and the other one is too big to calculate if it only contains 3, 5, and 7.

Since you only have 3, 5, and 7, I’m going to determine that the number is multiplied by 3, 5, and 7. As long as the number is less than the target number, the initial definition of sum=0 and the counter sum++ will print the result.

Development:

  • #include

    pow(2,k), can calculate 2 to the k
  • Target number is too large for int storage, change to long Longg int storage

Four, coding implementation

#include <iostream>
#include<math.h>// Pow header file
using namespace std;
int main(a)
{
	int i,j,k,sum=0;/ / initialization
	long long int n=59084709587505;// The target number is too large for int storage, change to long longg int storage
	for(i=0;pow(3,i)<=n; i++)// The first layer to the power of 3
	{
		for(j=0;pow(5,j)<=n; j++)// The second layer is 5
		{
			for(k=0;pow(7,k)<=n; k++)// The third layer to the power of 7
			{
				if(pow(3,i)*pow(5,j)*pow(7,k)<=n)// All the powers multiplied are less than the target number
				{
					sum++;//sum++
				}
			}
		}
	}
	cout<<sum- 1;// Because 0, 0, 0 doesn't count
    return 0;
}
Copy the code

5. Output results

The output is 1905