Circular Primes - Oleksandr Yolkin

circular primes

Я решил добавить в блог новую рубрику под названием Euler Project. Время от времени встречаются интересные задачки для программистов и не только, решить которые очень интересно и полезно. Поэтому сюда я буду выкладывать все, кто касается данной тематики – от обычных методов сортировки до задач на собеседованиях во всем известные компании а ля “если бы вы были карандашом и попали в блендер, как бы вы выбирались”. Также сюда относятся задачи проекта Эйлер такие как, например, Circular Primes.

Открывает рубрику задача из проекта Эйлер – Circular Primes.

Проект “Эйлер” — это набор интригующих задач по математике и программированию, для решения которых, однако, недостаточно одной только математической интуиции. Разумеется, математика поможет прийти к красивому и элегантному решению, но для успешного решения большинства задач без навыков программирования не обойтись.

Условие задания взято с сайта beatmycode.com, там же проводилось тестирование.

A number is called a circular prime if all of its rotations (rotations of their digits) are primes themselves. For example the prime number 197 has two rotations: 971, and 719. Both of them are prime, so all of them are circular primes. There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below N if 1 <= N <= 1000000?

В переводе на русский речь идет о круговых простых числах. Число считается простым, если оно делится без остатка на 1 и самого себя. Простое круговое число например 197, потому что как его не крути – 971 и 719 тоже являются простыми числами.

Задача состоит в том, чтобы посчитать сколько круговых простых чисел находится в диапазоне от 1 до 1000000?

Ничто не сравнится с удовлетворением от решения задачи, над которой вы ломали голову не один час. Конечно, желая поделиться своим озарением с другими, я действую из лучших побуждений, но увы, скорее всего я окажу вам медвежью услугу. Настоящее обучение — это активный процесс, одно дело наблюдать за процессом, и совсем другое — переживать этот опыт самому.

Реализация на Objective-C. Убедитесь, что вы сделали все возможное и невозможное, прежде чем заглянуть в решение.

//
//  main.m
//  CircularPrime
//
//  Created by Alexander Yolkin on 3/10/16.
//  Copyright © 2016 Iolkin. All rights reserved.
//

#import <Foundation/Foundation.h>

/**
 * return YES if number is Prime
 */
BOOL isPrime(NSUInteger number)
{
    if (number < 2) return NO;
    if (number == 2) return YES;
    if (number % 2 == 0) return NO;
    
    double limit = sqrt(number);
    
    for (NSUInteger i = 3; i <= limit; i += 2)
    {
        if ((number % i) == 0) return NO;
    }
    return YES;
}

/**
 * main function
 */
int main(int argc, const char * argv[])
{
    @autoreleasepool {
        NSUInteger N = [@"BMC_TEST_INPUT_MAGIC" integerValue];
        N = 1000000;
        NSUInteger circPrimes = 0;
        
        NSMutableArray* primesArr = [NSMutableArray array];
        for (NSUInteger i = 2; i < N ; i++)
        {
            if (isPrime(i)) [primesArr addObject:@(i)];
        }
        
        for (NSNumber* prime in primesArr)
        {
            NSString *primeStr = [NSString stringWithFormat:@"%@", prime];
            BOOL isCircullar = YES;
            for (NSUInteger i = 0; i < primeStr.length - 1; i++)
            {
                NSString *newPrime = [primeStr substringFromIndex:1];
                newPrime = [newPrime stringByAppendingString:[primeStr substringToIndex:1]];
                
                if (!isPrime([newPrime intValue])) {
                    isCircullar = NO;
                    break;
                }
                primeStr = newPrime;
            }
            if (isCircullar) circPrimes++;
        }
        printf("%lu\n", (unsigned long)circPrimes);
    }
    return 0;
}

// main.m

// CircularPrime

// Created by Alexander Yolkin on 3/10/16.

#import <Foundation/Foundation.h>

/**

* return YES if number is Prime

BOOL isPrime(NSUInteger number)

{

if (number < 2) return NO;

if (number == 2) return YES;

if (number % 2 == 0) return NO;

double limit = sqrt(number);

for (NSUInteger i = 3; i <= limit; i += 2)

{

if ((number % i) == 0) return NO;

}

return YES;

}

/**

* main function

int main(int argc, const char * argv[])

{

@autoreleasepool {

NSUInteger N = [@"BMC_TEST_INPUT_MAGIC" integerValue];

N = 1000000;

NSUInteger circPrimes = 0;

NSMutableArray* primesArr = [NSMutableArray array];

for (NSUInteger i = 2; i < N ; i++)

{

if (isPrime(i)) [primesArr addObject:@(i)];

}

for (NSNumber* prime in primesArr)

{

NSString *primeStr = [NSString stringWithFormat:@"%@", prime];

BOOL isCircullar = YES;

for (NSUInteger i = 0; i < primeStr.length - 1; i++)

{

NSString *newPrime = [primeStr substringFromIndex:1];

newPrime = [newPrime stringByAppendingString:[primeStr substringToIndex:1]];

if (!isPrime([newPrime intValue])) {

isCircullar = NO;

break;

}

primeStr = newPrime;

}

if (isCircullar) circPrimes++;

}

printf("%lu\n", (unsigned long)circPrimes);

}

return 0;

}

Показать меньше

Unit test beatmycobe.com – 100/100