Pure prime number

Create an array to record whether each bit is a prime number or not

Traversing through each number, if it is a prime number, then all the numbers that are multiple of its integer are not prime numbers, set the filter directly in the array, and then judge if the prime number is pure, just need to judge if it is 2,3,5,7 bit by bit.

Why only judge integers of prime numbers?

Because for a nonprime number, its integer multiple must also be an integer multiple of a certain prime number, all must have been traversed, so there is no need to repeat the traversal

package daily;

import java.util.ArrayList;
import java.util.Arrays;

public class day3_8_1 {
static int N = 20210605;
public static boolean[] nums = new boolean[N + 1];// Used to record whether each bit is a prime number or not

public static void main(String[] args) {
int ans = 0;
Arrays.fill(nums, true);
nums[0] = false;
ArrayList<Integer> list = new ArrayList<>();// Save all pure prime numbers because you look at them yourself

for (int i = 2; i < nums.length; i++) {
if (nums[i] == true) {
// Will be filtered out all times the prime number
int j = i;
while (j < nums.length) {
nums[j] = false;
j = j + i;
}

// Determine if the number is pure prime
if (isPurePrime(i)) {
ans++;
}
}

}
// System.out.println(list); This is just to see what numbers you need to comment out when submitting
System.out.println(ans);
}

/**
* Determine if a number is pure prime, as long as you decide whether it is prime bit by bit
*
* @param i
* @return
*/
private static boolean isPurePrime(int i) {
while (i > 0) {
int rightBit = i % 10;
if (!(rightBit == 2 || rightBit == 3 || rightBit == 5 || rightBit == 7)) {
return false;
}
i = i / 10;
}
return true;
}
}


Minimum weight

When we add a weight, we are sure to want him to express more data range, so we use a little greedy idea here

If the range we can now represent is [ 1 , . . . , range ] [1,...,\text{range}] [1,...,range], so if we insert another weight, the maximum range he can represent is [ 1 , . . . , range , w − r a n g e , . . . , w , . . . r a n g e + w ] [1,...,\text{range},w-range,...,w,...range+w] [1,...,range,w_range,...,w,...range+w], based on the continuous relationship, we can get r a n g e + 1 = w − r a n g e range+1=w-range range+1=w_range, so there is w = 2 ∗ r a n g e + 1 w=2*range+1 w=2_range+1, the maximum representable range becomes when a weight is inserted 3 ∗ r a n g e + 1 3*range+1 3∗range+1

package daily;

import java.util.Scanner;

public class day3_8_2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
int range = 1; // range
int res = 1; // Number of weights
while (range < n) {
range += (range + range + 1);
res++;
}
System.out.println(res);
}
}


irrigation

Using a queue to simulate the irrigation sequence, when irrigating a node, determine if the four surrounding nodes are within the farm range and join the queue if they are within the farm range and have not been irrigated

A Node class is created to represent each node with three attributes, its line number, column number, and the time it takes to irrigate it, making it easy to tell if the nodes around it need not be irrigated to

Another small trick is used in the code: using arrays to simulate the top, bottom, left, and right directions is equivalent to four if statements being reduced and the code looks a little more streamlined

package daily;

import java.util.Deque;
import java.util.Scanner;

public class day3_8_3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
boolean[][] farm = new boolean[n][m];// Farm size, indicating whether or not it has been irrigated

Deque<Node> nodeDeque = new LinkedList<>();// Create a queue to simulate irrigation by time
int t = sc.nextInt();
while (t > 0) {
t--;
int r = sc.nextInt() - 1;
int c = sc.nextInt() - 1;
nodeDeque.addLast(new Node(r, c, 0));// The location of the book tube is irrigated by default

farm[r][c] = true;// The marker has been irrigated
}
int k = sc.nextInt();
sc.close();

int ans = 0;

// Four irrigation directions per plot, use this to avoid writing four if
int[][] direction = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
while (!nodeDeque.isEmpty()) {
ans++;
Node node = nodeDeque.removeFirst();
// This means that when the time is over, you will no longer join its neighbors.
if (node.k == k) {
continue;
}
// Traverse it in four directions
for (int i = 0; i < direction.length; i++) {
int newR = node.r + direction[i][0];
int newC = node.c + direction[i][1];

// New nodes must be farm-wide and not irrigated
if (newR >= 0 && newR < n && newC >= 0 && newC < m && farm[newR][newC] != true) {
// Time is the current node's time+1
nodeDeque.addLast(new Node(newR, newC, node.k + 1));
}
}
}
System.out.println(ans);
}
}

class Node {
int r;// That's ok
int c;// column
int k;// Time to Irrigate Here

public Node(int r, int c, int k) {
super();
this.r = r;
this.c = c;
this.k = k;
}
}


Keywords: Java Algorithm

Added by greens85 on Wed, 09 Mar 2022 19:02:44 +0200